[파이썬] 단계별 백준 문제 풀기 - 1932 동적 계획법 1 (정수 삼각형)

문제링크

1932번: 정수 삼각형

---

<<코드블럭>>

import sys
n = int(sys.stdin.readline())
dp = [[0]*i for i in range(1,n+1)]
origin = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
dp[0][0] = origin[0][0] #맨 윗줄을 dp 리스트에 먼저 넣어주고 시작

for i in range(n): #0부터 4까지, 0,1,2,3,4
    for j in range(i+1): # j는 i가 0일때, 0 / i가 1일때, j는 0,1 / i가 2일때 j는 0,1,2 / i가 3일때 j는 0,1,2,3 /i가 4일때 j는 0,1,2,3,4
        if j == 0 : #제일 첫번째열에 있는 값은 그 위에 값과 더해주면 됨
            dp[i][j] = origin[i][j] + dp[i-1][j]
        elif j == i : #제일 마지막열에 있는 값은 그 위에 값과 더해주면 됨
            dp[i][j] = origin[i][j] + dp[i-1][j-1]
        else: #가운데 있는 값들은 위에 2개의 값과 자신을 각각 더해서 최대값을 구해주면 됨
            dp[i][j] = max(origin[i][j] + dp[i-1][j-1], origin[i][j] + dp[i-1][j])

#마지막행의 최대값을 출력
print(max(dp[n-1]))

<<결과값>>

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

30

---

이전에 풀었던 RGB거리와 비슷한 문제였다. RGB거리는 최솟값의 합이라면, 이 문제는 최댓값의 합이었다. 

dp 배열을 0으로 초기화해주고(여기에 합의 값을 담을 예정), origin 리스트에는 주어진 input값을 그대로 넣었다.

dp리스트의 제일 최초의 값은 역시나 origin 리스트의 값과 같다.

 

이제 0행부터 4행까지 for문을 돌아준다. for문의 첫째줄은 행이고, 두번째 for문은 열이다.

if j == 0 : #제일 첫번째열에 있는 값은 그 위에 값과 더해주면 됨
    dp[i][j] = origin[i][j] + dp[i-1][j]
elif j == i : #제일 마지막열에 있는 값은 그 위에 값과 더해주면 됨
    dp[i][j] = origin[i][j] + dp[i-1][j-1]
else: #가운데 있는 값들은 위에 2개의 값과 자신을 각각 더해서 최대값을 구해주면 됨
    dp[i][j] = max(origin[i][j] + dp[i-1][j-1], origin[i][j] + dp[i-1][j])

 

 if 문 : 제일 첫번째의 값은 바로 위의 값과 자신의 값을 더해주면 된다.

elif 문: 마지막 값도 바로 위의 값과 자신의 값을 더해주면 된다.

else문: 그 외의 모든 중간값은 위에 값 두개와 자신의 값을 더한 값 중, 최대값(max)을 골라주면 된다.

 

 

그리고 제일 마지막줄(4행)에서 최대값을 출력해주면 된다!