[Python] 정수 삼각형 - 백준 (DP)

해당 글은 백준 1932번 문제 '정수 삼각형'을 다룬다.

문제

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

1932번: 정수 삼각형

 

설명

이전 층의 데이터를 사용해서 각 층의 데이터를 업데이트 하는 방식으로 진행하였다.

가장 꼭대기 층일때는 값만 저장하고 continue를 통해 for문을 넘어가고

다음 층 부터는 첫번째 원소값일때, 마지막 원소값일때, 그외 중간값일때로 if문으로 나눠서 각각 계산하여 업데이트 하였다.

마지막으로 계산된 층에서 최대값을 출력하였다.

 

다른 방법으로는 DP로 쉽게 풀 수 있다. 아래행으로 내려오면서 계속해서 업데이트를 진행하는 방식이다.

 

코드

n = int(input())

for i in range(n):
    floor_data = list(map(int, input().split()))
    if i == 0:
        pre_floor_data = floor_data[:]
        continue
    for j in range(len(floor_data)):
        if j == 0:
            floor_data[j] += pre_floor_data[0]
        elif j == len(floor_data)-1:
            floor_data[j] += pre_floor_data[j-1]
        else:
            left_sum = floor_data[j]+pre_floor_data[j-1]
            right_sum = floor_data[j]+pre_floor_data[j]
            floor_data[j] = max(left_sum, right_sum)
    pre_floor_data = floor_data[:]

print(max(pre_floor_data))

코드 (DP)

n = int(input())
dp = []

for i in range(n):
    dp.append(list(map(int, input().split())))

for i in range(1, n):
    for j in range(0, i+1):
        if j == 0:      # 가장 왼쪽 값
            dp[i][0] += dp[i-1][0]
        elif j == i:    # 가장 오른쪽 값
            dp[i][j] += dp[i-1][j-1]
        else:
            dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])
print(max(dp[n-1])) # n-1행에서 최댓값