[알고리즘] 백준 1932 - 정수 삼각형

문제

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

1932번: 정수 삼각형

 

풀이

보자마자 DP라고 생각했다. 백준 1149번 RGB거리랑 거의 똑같은 문제고 해당 문제를 풀었던 적 있어서 그 문제 풀이대로 풀었다. 문제를 3분컷하면 기분이 참..좋습니다.

코드를 더 효율적으로? 짧게? 짤 수 있을 것 같긴한데 짧은 코드라고 해서 무조건 좋은 코드는 아니라고 생각해서... 그냥 이대로 제출~

 

 

코드

n = int(input())
arr = []
for _ in range(n):
    tmp = list(map(int,input().split()))
    arr.append(tmp)

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

print(max(dp[-1]))