📖Problems
프로그래머스 - 고득점 kit - DP - 정수 삼각형 (Level3)
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 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 |
🔍Institution
답이 어떻게 30이 나왔을까?
그때그때 가장 큰 숫자, 당장 눈 앞에 큰 숫자를 따라 가면 안 된다!!
전체적으로 큰 숫자를 구해야 한다!
동적계획법 문제로 분류되어 있기 때문에 dp 리스트를 만들고, 위에서부터 아래로 더해가는 누적해가는 방식으로 풀이를 진행하였다.
🔍Approach
1
2
3
4
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
| i / j | 0 | 1 | 2 | 3 | 4 | | — | — | — | — | — | — | | 0 | 7 | 0 | 0 | 0 | 0 | | 1 | 7+3=10 | 7+8 = 15 | 0 | 0 | 0 | | 2 | 10+8=18 | max (10+1, 15+1) 16 | 15+0=15 | 0 | 0 | | 3 | 18+2=20 | max (18+7, 16+7) 25 | max (16+4, 15+4) 20 | 0+0=0 | 0 | | 4 | 20+4 =24 | max (20+5, 25+5) 30 | max (25+2, 20+2) 27 | max (20+6, 0+6) 26 | 5 |
1
2
3
4
5
7
10 15
8 1 0
2 7 4 4
4 5 2 6 5
1
2
3
4
5
7
10 15
18 16 15
2 7 4 4
4 5 2 6 5
1
2
3
4
5
7
10 15
18 16 15
20 25 20 19
4 5 2 6 5
1
2
3
4
5
7
10 15
18 16 15
20 25 20 19
24 30 27 26 24
위의 방식을 토대로, 아래와 같이 flow를 짤 수 있다.
dp를 먼저 0으로 초기화한다.dp[0][0]에는 값이 미리 있어야 반복문 안에서 처리가 가능하므로triangle[0][0]의 값을 저장한다.- 이중for문을 이용해
dp테이블에 값을 저장한다 (j는 i만큼 반복하기 때문에 범위는 i+1)- 양쪽 끝 숫자들은 처음 혹은 끝의 영향만 받기 때문에
max()로 비교 없이 누적해가면 된다.- 처음인 경우 →
dp[i][j] = dp[i-1][j] + triangle[i][j] - 마지막인 경우(
i == j) →dp[i][j] = dp[i-1][j-1] + triangle[i][j]
- 처음인 경우 →
- 가운데에 있는 숫자들은 위의 2개의 수를 비교해야 하기 때문에
max()를 이용해 더했을 때 더 큰 숫자를 저장한다.
- 양쪽 끝 숫자들은 처음 혹은 끝의 영향만 받기 때문에
- 가장 마지막
i에서 max값을 구해야 하므로 그냥max(dp)가 아니라max(dp[-1])를 return한다.
🚩My submission
- dp를 사용한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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(0, i+1):
if j == 0:
dp[i][j] = dp[i-1][j] + triangle[i][j]
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
- 하지만 여기서 잘 보면 굳이
dp리스트를 사용하지 않아도 된다. triangle이dp의 역할까지 하기 때문이다!
dp없이 풀기 → triangle 이용하기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def solution(triangle):
# 높이
for i in range(1, len(triangle)):
# 각 행의 요소
for j in range(0, i+1):
if j == 0:
triangle[i][j] = triangle[i-1][j] + triangle[i][j]
elif i == j:
triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]
else:
triangle[i][j] = max((triangle[i-1][j-1] + triangle[i][j]), (triangle[i-1][j] + triangle[i][j]))
answer = max(triangle[-1])
return answer
🚩Others submission
JB선배 - 재귀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def dfs(height, t, n):
if height == n:
return t
for i in range(len(t[height])):
if i == 0:
t[height][i] = t[height-1][i] + t[height][i]
elif i == len(t[height]) - 1:
t[height][i] = t[height-1][i-1] + t[height][i]
else:
t[height][i] = max(t[height-1][i-1]+t[height][i], t[height-1][i] + t[height][i])
return dfs(height+1, t, n)
def solution(triangle):
t = dfs(1, triangle, len(triangle))
return max(t[-1])
💡TIL
- 우선 제한시간 1시간 안에 (거의) 혼자 힘으로 풀어서 뿌듯하다.
DP에 무엇을 저장할지 고민하다 보니, 누적값을 넣어야 한다는 것을 알게 되었고 이 과정에서 나열해보는 게 가장 좋은 것 같댜.- 처음부터 경우를 나누어 볼 수도 있었지만 나는 큰 틀을 먼저 짠 후, 테스트케이스를 모두 대입해보며 부족한 점을 코드에 채워넣는 식으로 했다.