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

문제

 

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

1932번: 정수 삼각형

 

 

풀이

 

처음에는 result라는 1차원배열을 따로 두어 result[k]가 k층까지 더한 값의 최대값으로 설정하려고했다. 만약 k층까지는 최대값이지만 다음층에서 더할 수 있는 숫자가 매우 작다면 k + 1층에서는 result[k]값이 쓸모가 없게된다. 

그래서 이렇게 하지 않고 반복문을 통해 triangle변수의 각 자리를 누적된 합으로 정해주기로 하였다.

 

예시를 들어보면, 1층에 7이 있고 2층에 3과 8이 있다고 하자. 그러면 1층에는 7이 그대로 있고, 2층의 왼쪽자리엔 7과 3을 더한 10이 들어가고 오른쪽 자리엔 7과 8을 더한 15가 들어가게 되는 것이다.

 

이를 통해 규칙을 찾아보면 맨 왼쪽과 맨 오른쪽은 기존의 triangle의 수에 이전 층의 맨 왼쪽값과 오른쪽 값을 각각 더한 값이 된다. 그리고 중간에 있는 것들은 더해질 수 있는 경우가 두 가지가 있을 수 있다. 그렇기때문에 max값을 이용해서 더 큰 값을 자리에 넣어주도록 하였다.

 

마지막 줄의 최대값을 구하면 결과를 출력할 수 있다.

import Foundation

let n = Int(readLine()!)!
var triangle: [[Int]] = []
for _ in 0..<n {
    triangle.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
for i in 1..<n {
    for j in 0...i {
        if j <= 0 {
            triangle[i][j] = triangle[i][j] + triangle[i - 1][j]
        } else if j > 0 && j <= i - 1 {
            triangle[i][j] = max(triangle[i - 1][j - 1] + triangle[i][j], triangle[i][j] + triangle[i - 1][j])
        } else {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i][j]
        }
    }
}
print(triangle[n - 1].max()!)

 

 

_____________________________________________________________________________________________________

 

 

어렵지 않게 규칙을 찾을 수 있어서 다행이다. 이 문제를 풀다보니 원티드 쇼미더코드 3회차의 신을 모시는 사당 문제도 비슷한 문제였구나하는 생각이 들었따.