[Algorithm/BOJ] 1932 - 정수 삼각형 (DP) Swift

문제 풀이:

맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 

-> 문제의 설명을 토대로 아래 그림으로 그려봤다. 

 

빨간색 화살표로 갈 수 있는 경로를 나타내고 파란색 글씨는 배열의 인덱스를 나타낸 것이다.

오른쪽 그림과 같이 인덱스가 0 -> 0,1  1 -> 1,2 의 규칙이 있다. 

이 규칙을 이용해서 맨 왼쪽라인의 경우, 맨 오른쪽 라인의 경우 그리고 그 외의 경우에 대해서 값을 위에서 아래로 더하는 방식으로 문제를 접근했다. 

그 외의 경우는 맨 왼쪽과 맨 오른쪽 라인의 사이 값은 갈 수 있는 2가지 경로 중 큰 값을 더했다.

마지막 행까지 다 더 했을 때의 결과는 아래의 그림과 같다.

마지막 행의 가장 큰 값이 최대 값이 된다.

 

코드: 

import Foundation

func solution() -> Int {
    let num = Int(readLine()!)!
    var triangle = [[Int]]()

    for _ in 0..<num {
        triangle.append(readLine()!.split(separator: " ").map { Int(String($0))! })
    }

    for i in 1..<num {
        for j in 0..<i+1 {
            // 맨 왼쪽, 인덱스가 0일 때
            if j==0 {
                triangle[i][j] += triangle[i-1][j]
            }
            // 맨 오른쪽, 인덱스가 i(끝일 때)
            else if j==i {
                triangle[i][j] += triangle[i-1][j-1]
            }
            // 그 외의 경우 맨 왼쪽가 맨 오른쪽 사이
            else {
                triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])
            }
        }
    }
    // 마지막 행의 제일 큰 값이 최대 값
    return triangle[num-1].max()!
}

print(solution())

/*
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
*/

문제:

1932번: 정수 삼각형