문제
프로그래머스 코딩테스트 고득점 Kit -
동적계획법(Dynamic Programming)
- Lv 2. 정수 삼각형 (Python)
https://school.programmers.co.kr/learn/courses/30/lessons/43105
코드 구현
def solution(triangle):
answer = 0
"""
<< triangle >>
7 (0,0)
3 (1,0) 8 (1,1)
8 (2,0) 1 (2,1) 0 (2,2)
2 (3,0) 7 (3,1) 4 (3,2) 4 (3,3)
4 (4,0) 5 (4,1) 2 (4,2) 6 (4,3) 5 (4,4)
---------
<< dp >>
7 (0,0)
10 (1,0) 15 (1,1)
18 (2,0) 11 vs 16 (2,1) 15 (2,2)
y가
0이면 -> x-1 인덱스에서 무조건 y가 0인 애가 더해짐
1이면 -> x-1 인덱스에서 y가 0인거나 1인거 중에서 더했을 때 더 큰거
2이면 -> x-1 인덱스에서 무조건 y가 1인 애가 더해짐
"""
# (x, y) 라고 하면 그 다음 y는 같은 y, y+1 인 곳으로 이동 가능
dp = [[0 for j in range(len(triangle[i]))] for i in range(len(triangle))]
dp[0][0] = triangle[0][0]
# 각 좌표값 (x, y)
for x in range(1, len(triangle)):
for y in range(len(triangle[x])):
if(x < 2): # x가 1일땐 triangle[0][0]이 각자 자기자신과 더해지면 끝
dp[x][y] = triangle[0][0] + triangle[x][y]
else:
# 밑에서 [x][y+1] 에 대한 값을 지정해주기 때문에 인덱스 에러가 나지 않기 위해 탈출문 설정
if(y >= len(triangle[x])-1):
break
dp[x][y] = max(dp[x][y], dp[x-1][y] + triangle[x][y]) # (현재 dp에 있는 값) vs (현재 dp의 위에 있는 값 + triangle의 현재 인덱스 값)
dp[x][y+1] = dp[x-1][y] + triangle[x][y+1] # 그 다음 비교를 위해 현재 dp 위에 있는 값을 미리 더해놓기
answer = max(dp[-1]) # 더해진 마지막 최종 값들의 max가 정답
return answer풀이
- 각 좌표값을
(x, y)라고 한다면,x가 1인거 까지는 비교가 필요없이 지정된다. x가 2인값부터는자기자신과위에서 대각선 왼쪽or오른쪽값과 더했을 때 둘 중 더 큰 값이 자기 자신의 인덱스에 들어가야한다.""" << triangle >> 7 (0,0) 3 (1,0) 8 (1,1) 8 (2,0) 1 (2,1) 0 (2,2) 2 (3,0) 7 (3,1) 4 (3,2) 4 (3,3) 4 (4,0) 5 (4,1) 2 (4,2) 6 (4,3) 5 (4,4) --------- << dp >> 7 (0,0) 10 (1,0) 15 (1,1) 18 (2,0) 11 vs 16 (2,1) 15 (2,2) ... """- 위의 인덱스 값들을 보며 예를 들면, (2,1) 자리에서는
10 + 1vs15 + 1중 누가 더 큰지 비교되어15 + 1의 값이 들어가게 되는데, for문 동작에 의해x가 2,y가 0일 때
→ 우선10 + 1이dp[x][y+1]에 먼저 들어가 있고
(10 + 1==dp[1][0] + triangle[2][1]==dp[x-1][y] + triangle[x][y+1]) 그 다음 x가 2, y가 1일 때
기존에 들어가있던 10 + 1 을 15 + 1과 비교해야한다.
(15 + 1==dp[1][1] + triangle[2][1]==dp[x-1][y] + triangle[x][y]) 둘 중 더 큰 값으로 갱신되어야 하기 때문에max()를 통해 업데이트 해준다.
- 최종적으로 제일
dp배열에 가장 마지막 줄에서 제일 큰 값이 삼각형을 대각선으로 내려오면서 더했던 값들의 최댓값이 된다.
DP 참고자료
데굴데굴 뚝딱뚝딱 개발기록