[이코테] 다이나믹프로그래밍 - 정수 삼각형

 

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

1932번: 정수 삼각형

사고과정

• 저번에 푼 금광 문제랑 매우 유사한 유형이었지만 시간 내에 풀지 못했다. 풀이의 아이디어만 보고 다시 돌아가서 풀 수 있었다. 금광 문제 때랑 또 똑같이 풀려고 어리석은 짓을 했다..(실력이 늘지 않고 있는 건가..?흑..)
• DP 점화식을 구현할 때, '다음 단계의 입장'에서 보는 것을 잊지 말아야 한다! 예를 들어, 단계가 진행된다고 하면 1단계에서 -> 2단계를 보는 것이 아니라 2단계의 관점에서 1단계를 보고 점화식을 구현해야 한다! 

풀이(스스로 못 푼 풀이)

import sys

n = int(input())
array = []
for i in range(n):
    data = list(map(int, input().split()))
    array.append(data)

for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            up_left = 0
        else:
            up_left = array[i-1][j-1]
        if j == i:
            up = 0
        else:
            up = array[i-1][j]
        array[i][j] = array[i][j] + max(up, up_left)

result = max(array[n-1])
print(result)