알고리즘
[Swift] 백준 정수 삼각형
고고
2022. 2. 4. 15:28
문제: https://www.acmicpc.net/problem/1932
1932번: 정수 삼각형
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
www.acmicpc.net
코드
import Foundation
let N = Int(readLine()!)!
var dp = [[0, 0]]
for _ in 0..<N {
dp.append(readLine()!.split(separator: " ").map { Int($0)! })
}
for i in 1..<dp.count {
for j in 0..<dp[i].count {
if j == 0 { // 맨 왼쪽거는
dp[i][j] = dp[i][j] + dp[i - 1][j]
} else if j == dp[i].count - 1 { // 맨 오른쪽 거
dp[i][j] = dp[i][j] + dp[i - 1][j - 1]
} else {
dp[i][j] = max(dp[i][j] + dp[i - 1][j], dp[i][j] + dp[i - 1][j - 1])
}
}
}
//print(dp)
var result = dp[N].max()!
print(result)