[백준/Python] 1932 정수삼각형

문제는 여기

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = []
dp = [[0]*(n+2) for _ in range(n)]

for i in range(n):
    l = []
    l.append(0)
    l.extend(list(map(int,input().split())))
    l.append(0)

    arr.append(l)

dp[0][1] = arr[0][1]

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

print(max(dp[n-1]))

기록할 점

• 며칠 전에 풀었던 11048 이동하기 문제와 매우 유사하다고 생각했다

• 삼각형 옆 부분에 0이라는 값을 임의로 넣어주고, 왼쪽 오른쪽 대각선 값 중에서 큰 값과 현재 위치의 값을 dp 값으로 넣어주었다
  
  마지막 줄에 있는 값 중 최댓값이 문제에서 요구하는 값이기 때문에 그 값을 리턴해주었다

• 풀고나서 다른 사람들 풀이보니까 이렇게 풀은 사람은 거의 없는 것 같다 (약간 당연함)
  왜냐하면 내 풀이처럼 풀게되면 맨 왼쪽과 맨 오른쪽에 있는 값은 의미없는 연산을 하게 되기 때문이다 .. 😇
  

이런 풀이법도 있답니다.
하지만 다시 푼다면 맨 왼쪽 / 중간 값들 / 맨 오른쪽 인 경우를 나눠서 풀 것 같다!