[백준/DP] 1932번: 정수 삼각형 (실버 1, python)

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

1932번: 정수 삼각형

아이디어

DP문제이다.

빨간색 표시한 자리를 [i][j]라고 할 때 [i][j]의 최댓값은 [i-1][j-1]과 [i-1][j] 중 큰 값과 [i][j]의 값을 더해서 구한다.

즉, 아래처럼 표현할 수 있다.

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + datas[i][j]

 

하지만 구한 식은 위 경우에 인덱스 에러를 일으키게 된다. 양 끝은 [i-1][j-1] 이 없거나, [i-1][j]가 없기 때문이다.

이를 해결하기 위한 두 가지 방법이 있다.

첫 번째는 예외처리를 하는거다. 

        if j == 0: dp[i][j] = dp[i-1][0] + datas[i][j]
        elif j == (size - 1): dp[i][j] = dp[i-1][-1] + datas[i][j]

이처럼 만약 양 끝에 있는 데이터라면 max를 하지 않고 바로 위 데이터만 더해주도록 한다.

 

두 번째 방법은 삼각형의 양 끝에 0을 추가하는거다.

위 그림처럼 양 끝에 0을 추가하면 기존에 찾은 식을 그대로 사용할 수 있다.

 

 

전체 코드

n = int(input())
datas = [[int(x) for x in input().split()] for _ in range(n)]
dp = [[0 for _ in datas[i]] for i in range(n)]
dp[0] = datas[0]

for i in range(1, n):
    size = len(datas[i])
    for j in range(size):
        if j == 0: dp[i][j] = dp[i-1][0] + datas[i][j]
        elif j == (size - 1): dp[i][j] = dp[i-1][-1] + datas[i][j]
        else:
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + datas[i][j]

print(max(dp[-1]))