[Swift][DP] 백준 1932번 (정수삼각형)

요구능력 : DP에 대한 이해

 

코드설명 : 

 

문제를 읽고 우선적으로 생각해볼 수 있는건 dp[i]를 구하려면 이전에 어떤 값을 골랐는지가 중요하다는것이다.

삼각형에서 한줄을 i줄이라고 한다면 몇번째 수를 선택했는지가 중요한것이다.

이것을 보고 dp는 2차원 배열로 이루어지겠구나를 생각했다.

 

조건은 왼쪽대각선 혹은 오른쪽대각선으로만 선택할 수 있는것이다.

문제의 예제를 보고 8, 1, 0이 있는 줄을 dp[i]라고 생각해보면 이전 줄에 3, 8이 있다.

우선 8을 선택했을 때의 최대값을 구하기 위해서는 3에서 내려오는 방법밖에는 없다.

왼쪽 대각선으로 내려오는 것 밖에 없는것이다.

 

다음으로 1을 생각해보자.

dp[i][1]을 구하는것인데 1은 왼쪽대각선과 오른쪽대각선 2가지가 모두에서 내려올 수 있다. 

 

다음으로 0을 생각해보면

dp[i][2]를 구하는것인데 0은 위에서 오른쪽대각선으로 내려오는것밖에없다.

 

이것을 조건으로 보면

왼쪽 끝에있는것(j가 0일때)은 경우의 수가 위에서 왼쪽대각선으로 내려오는것밖에 없구나.

배열의 인덱스상 왼쪽대각선으로 내려오는건 현재 보고있는 dp[i][j]의 인덱스와 같다.

따라서 점화식은 dp[i][j] = dp[i - 1][j] + arr[i][j] 이렇게 나온다.

 

왼쪽, 오른쪽에서 내려오는경우에는

왼쪽에서 내려올때와 오른쪽에서 내려올때중 최대값을 가져오면 되므로

dp[i][j] = max(dp[i - 1][j] + arr[i][j], dp[i - 1][j - 1] + arr[i][j])

이다.

 

오른쪽에서 내려올경우 한칸 작은 이전dp를 구하면되므로

dp[i][j] = dp[i - 1][j - 1] + arr[i][j] 과 같은 식이 나오게된다.

 

 

후기 : 문제에 대놓고 조건을 줘서 금방풀었다..

let n = Int(String(readLine()!))!
var arr:[[Int]] = [[]]
var dp = Array(repeating: Array(repeating: 0, count: 501), count: 501)
for _ in 1...n {
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

dp[1][0] = arr[1][0]
for i in stride(from: 2, through: n, by: 1){
    for j in 0..<arr[i].count{
        if j == 0{
            dp[i][j] = dp[i - 1][j] + arr[i][j]
        }else if j < arr[i].count - 1{
            dp[i][j] = max(dp[i - 1][j] + arr[i][j], dp[i - 1][j - 1] + arr[i][j])
        }else if j == arr[i].count - 1{
            dp[i][j] = dp[i - 1][j - 1] + arr[i][j]
        }
        
    }
}
print(dp[n].max()!)