boj1932 - 정수삼각형 (python)

문제

코드

import sys
input = sys.stdin.readline

n = int(input())
d = [[0 for _ in range(n+1)] for _ in range(n)]
for i in range(0, n):
    dn = list(map(int, input().split()))
    for j in range(1,i+2):
        d[i][j] = dn[j-1]
# print(d)
for i in range(1, n):
    for j in range(1, i+2):
        d[i][j] = max(d[i-1][j], d[i-1][j-1]) + d[i][j]
print(max(d[n-1]))

설명

7
10 0
0 0 100
1 2 3 4
일 경우 위에서 부터 가장 큰 것을 선택하는 것이 정답이 아님.
따라서 현재 위치가 d[i] 일 때 이전 행 d[i-1] 에서 올수 있는 경로 중 큰것을 선택.

점화식 : d[i][j] = max(d[i-1][j-1], d[i-1][j]) + d[i][j]
이때 j ==0 인 경우 d[i-1][j-1]에서 인덱스 에러가 나는 것을 막기위해 d[i][0] 을 모두 0으로 채움.

다른 코드

n = int(input())
for i in range(n):
    arr = list(map(int, input().split()))

    if i!=0:
        arr[0] = arr[0] + dp[0]
        arr[-1] = arr[-1] + dp[-1]

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

설명

아이디어는 같으나 더 빠르고 간단
처음과 마지막 원소는 이전 행의 처음, 마지막 원소에 자신을 더함
그 사이에 있는 애들은 이전 행의 두 경로중 큰것과 자신을 더함