알고리즘 - Python / 백준 - 1932번 : 정수 삼각형

1932번: 정수 삼각형 (acmicpc.net)

1932번: 정수 삼각형

 

---

풀이

• 삼각형 모양으로 이루어진 수열을 위에서 부터 더했을 때 , 가장 큰 값을 찾는 문제이다.
• 모든 경우를 다 해보아야 하고 위쪽의 삼각형을 더한 결과를 아래쪽에도 사용하므로 dp로 접근해 해결하였다.
• 삼각형은 모서리 쪽이 아닌 이상 위의 2개의 수중에서 선택을 해야하고 그떄 max값을 가지는 수를 선택해 dp 배열안에 가장 큰 수의 경우만 저장될 수 있도록 한다.
• 이후 마지막 dp배열에서 max 값을 찾고 출력하면 된다.

 

import sys
n = int(sys.stdin.readline())
stack = []
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(n):
    stack.append(list(map(int,sys.stdin.readline().split(" "))))
dp[0][0] = stack[0][0]
for i in range(1,n):
    for t in range(0,i+1):
        if t == 0:
            dp[i][t] = dp[i-1][t] + stack[i][t]
        elif t == i:
            dp[i][t] = dp[i-1][t-1] + stack[i][t]
        else:
            dp[i][t] = stack[i][t] + max(dp[i-1][t],dp[i-1][t-1])
print(max(dp[n-1]))

---