[Swift] BOJ 1932 정수 삼각형

BOJ 1932 정수 삼각형

 

접근 방식

 

위에서 아래로 내려오며 각 칸까지의 최대 합을 누적하는 DP. 각 칸은 바로 위 두 칸(왼쪽 위, 오른쪽 위) 중 큰 값에 자기 값을 더함. 양 끝 칸은 위에서 올 수 있는 칸이 하나뿐이라 따로 처리함.

 

스스로 점화식을 찾아서 풀었음. solved.ac 기준 난이도는 실버 1이었음.

 

풀이 과정은 아래 사진을 참고.

 

 

시행착오

 

dp[1], dp[2]를 먼저 세팅하는 습관이 있는데, 입력이 1일 때 두 번째 행이 없어 dp[1] 세팅에서 인덱스 범위를 벗어남. 코드에서 if input >= 2로 감싸 막음.

 

print에서 dp.last!.max()가 옵셔널로 나오므로 언래핑하지 않으면 틀렸다고 나옴.

 

코드

 

        let input: Int = Int(readLine()!)!
        var list = [[Int]]()
        var dp = [[Int]](repeating: [Int](repeating: 0, count: input), count: input)
        
        for _ in 0..<input {
            let v = readLine()!.components(separatedBy: " ").map { Int($0)! }
            list.append(v)
        }
//        print(list)
        dp[0][0] = list[0][0]
        
        if input >= 2 {
            dp[1][0] = dp[0][0] + list[1][0]
            dp[1][1] = dp[0][0] + list[1][1]
        
            for row in 2..<list.count {
                list[row].enumerated().forEach {
                    let col = $0.offset
                    if col == 0 { // 처음
                        dp[row][col] = dp[row-1][0] + list[row][0]
                    } else if col == list[row].count-1 { // 끝
//                        print("끝입니다. \(col)")
                        dp[row][col] = dp[row-1][col-1] + list[row][col]
                    } else {
                        let pivot = max(dp[row-1][col-1], dp[row-1][col])
                        dp[row][col] = pivot + list[row][col]
                    }
                }
            }
        }
        
        print(dp.last!.max()!)