프로그래머스 - 정수 삼각형

문제

• 삼각형 꼭대기에서부터 바닥까지 이동할 때, 숫자의 합이 가장 큰 경우를 찾아라.
• 아래칸으로 이동할 때는 대각선 방향으로 왼쪽 한 칸 또는 오른쪽 한 칸으로만 이동이 가능하다.

 

제한사항

• 1 <= 삼각형의 높이 <= 500
• 0 <= 삼각형을 이루고 있는 숫자 <= 9999

 

문제풀이

1. 이 문제의 가장 작은 하위 문제는 다음 칸의 두 수 중 더 큰 수를 찾는 것이다.
2. 맨 아래 칸부터 왼쪽 오른쪽 중 큰 수를 윗칸의 숫자에 더해준다. 차례차례 더해주며 맨 윗쪽에 있는 하위 문제까지 해결한다.
3. 첫번째 칸에 있는 숫자를 반환한다.

윗칸의 숫자 중 큰 수를 아랫칸의 숫자에 가산해 주는 탑 다운으로도 풀 수도 있지만, 윗칸의 숫자는 아래칸보다 항상 1개 적기 때문에 맨 끝에 있는 숫자에 대해 예외처리를 해주어야한다. 그러므로 다운탑으로 풀어가는 것이 더 자연스럽고 코드도 더 간결하게 짤 수 있다.

 

function solution(triangle) {
    for (let i = triangle.length - 2; 0 <= i; i--) {
        for (let j = 0; j < triangle[i].length; j++) {
            triangle[i][j] += Math.max(triangle[i+1][j], triangle[i+1][j+1])
        }
    }
    return triangle[0][0]
}

 

시간복잡도: O(N^2), N이 500 이하로 제한되어 있으므로 O(1)

공간복잡도: O(1)