[프로그래머스] 정수 삼각형
문제
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
제한사항
- 삼각형의 높이는 1 이상 500 이하입니다.
- 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
입출력 예
| triangle | result |
|---|---|
| [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] | 30 |
풀이
이전에 풀었던 문제 유형이 탐욕법이었다보니 처음에는 그냥 Top에서부터 시작하여 매 갈림길에서 큰 값으로만 이동하면 풀릴 것이라는 안일한 생각을 했었다.
하지만 예시 입출력으로 해봤을 때 위 방법으로는 예시 출력과 같은 값을 얻을 수 없어서 다른 방법을 생각해내야 했다 (정말 다행인것이 예시케이스에서도 위 알고리즘이 성립했다면 빼도박도 못하고 함정에 빠질수도 있었다).
문제는 매 층마다 어느 갈림길을 통해 내려왔는지에 따라서 거쳐갈 수 있는 수가 제한된다는 것이다.
다음층에 어떤 큰 수가 있더라도 그 수를 거쳐갈 수 있는 루트로 내려오지 않았다면 그 수와 더해줄 수 없다.
때문에 층마다의 최대값을 저장하는 방법이 아닌 갈림길에 따른 최대값을 모두 저장하고 비교하는 것이 적절해보인다.
마지막에 1층에 도달하게 되면 1층에 있는 각 수에 도달하기까지의 거쳐온 값들의 합의 최대값이 나오게 되는데, 이 값들중 최대값을 반환하면 풀 수 있을 것으로 보인다!
아래와 같이 이렇게 2차원 리스트를 사용하여 각 층에서의 값들을 표현할 수가 있다.
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | 7 | ||
| 1 | 7+3 | 7+8 | |
| 2 | 7+3+8 | max(7+3+1, 7+8+1) | 7+8+0 |
중간의 수, 예를들어 2층의 1은 7->3을 거쳐서도 접근이 가능하고, 7->8을 거쳐서도 접근이 가능하다.
따라서 이 경우에는 두 방법중 거쳐간 숫자의 합이 더 큰 경우로 설정하는 것이 바람직하다.
3층에서는 7,4, 4층에서는 5,2,6의 값이 이 경우에 속하는데, 각 층의 첫번째 값과 마지막 값을 제외한 모든 자리는 거쳐간 숫자의 합이 더 큰 경우로 설정하면 된다.
이를 점화식으로 옮기면..
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | triangle[0,0] | ||
| 1 | triangle[0,0]+triangle[1,0] | triangle[0,0]+triangle[1,1] | |
| 2 | triangle[1,0]+triangle[2,0] | max(triangle[1,0]+triangle[2,1], triangle[1,1]+triangle[2,1]) | triangle[1,1]+triangle[2,1] |
이를 토대로 코드를 작성하면 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(triangle):
dp = [[0] * i for i in range(1, len(triangle)+1)]
dp[0][0] = triangle[0][0]
# 높이
for i in range(1, len(triangle)):
# 각 행의 요소
for j in range(i+1):
if j == 0:
dp[i][j] = dp[i-1][j] + triangle[i][0]
elif i == j:
dp[i][j] = dp[i-1][j-1] + triangle[i][j]
else:
dp[i][j] = max((dp[i-1][j-1] + triangle[i][j]), (dp[i-1][j] + triangle[i][j]))
answer = max(dp[-1])
return answer