알고리즘 문제(Swift) - 백준 - 1932 (정수 삼각형)

https://www.acmicpc.net/problem/1932

1. 문제의 재귀적인 구조 파악

• 맨 위부터 아래로 내려오면서 선택된 수의 합의 최대 값을 구하는 문제
• 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택

→ 다음으로 갈 수 있는 곳은 동일한 인덱스 또는 인덱스 + 1

 

위에서 index = 1을 선택했다면

다음 층에서 인덱스 1, 2 선택 가능

→ 현재 층의 인덱스 2는 이전 층의 인덱스 1과 인덱스 2에서 선택 받을 수 있음

 

2. 수식으로 표현

• f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + score[i]
• i: 삼각형의 층
• j: 층 내 모든 수

 

3. 초기값 처리 (기저 조건)

• 맨 왼쪽에 있는 수에서 f[i - 1][j - 1]을 하게 되면 인덱스 에러가 나므로 [0]을 추가해야 함

 

첫 번째 시도

let n = Int(readLine()!)!
var arr = [[0]]

for _ in 0..<n {
    arr.append([0] + readLine()!.split(separator: " ").map{Int($0)!})
}

var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1)

for i in 1...n {
    for j in 1...i {
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + arr[i][j]
    }
}

print(dp[n].max() ?? 0)