백준 1932번 정수 삼각형 파이썬

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

내 답안

import sys
input = sys.stdin.readline

n = int(input())
dp = [list(map(int,input().split())) for i in range(n)]

for i in range(n-1, 0, -1):
    for j in range(i):
        dp[i-1][j] += max(dp[i][j], dp[i][j+1])
        
print(dp[0][0])

---

 

Review

 

맨 아래서부터 둘 중의 한값중 큰 값을 그 윗 값에 더하는 것을 반복하면 될 것 같다고 생각했다.

 

무슨 소리인지 모르면 아래 그림을 참고하자.

 

예제 문제를 그림으로 설명 하자면

step1

 

저 하늘색을 2개의 초록색 중에 큰 값을 하늘색에 더한 값을 하늘색에 넣는 걸 계속 반복해 주면 된다.

Bottom-Up 방식으로 dp 배열을 갱신해 준다고 생각하자.

step2

 

이런식으로 갱신해 주다 보면

.

.

final step

 

이렇게 배열 값들이 바뀔 것이고

가상 최상단에 있는 루트 노드가 정답이 될 것이다.

 

for i in range(n-1, 0, -1):
    for j in range(i):
        dp[i-1][j] += max(dp[i][j], dp[i][j+1])

 

이 부분이 그림을 코드로 구현한 부분이다.

길이는 짧았지만 숫자 계산이 안되서 좀 애 먹었다,,