[백준] 1932번(정수 삼각형)

백준 1932번

최종 제출 코드

import sys

input = sys.stdin.readline

N = int(input().rstrip())
dp = [0]*N

for i in range(N):
  array = list(map(int, input().split()))
  
  for j in range(len(array)):
    if j==0:
      array[j] = dp[j] + array[j]
    elif j==len(array)-1:
      array[j] = dp[j-1] + array[j]
    else:
      array[j] = max(dp[j-1], dp[j]) + array[j]
      
  for k in range(len(array)):
    dp[k] = array[k]
    
print(max(dp))

.
◼ array와 dp 배열을 활용한다.

• 첫번째 원소인 경우, dp[j] + array[j]으로 array[j]값 업데이트
• 마지막 원소인 경우, dp[j-1] + array[j]으로 array[j]값 업데이트
• 이 외의 경우, dp[j-1]과 dp[j] 값 중 큰 값에 array[j]값을 더해 array[j]값 업데이트
• array의 모든 원소 값의 업데이트가 끝나면, 이 값을 dp에 복사해준다.

✔ 그림에는 편의상 dp를 바로 업데이트 하는 것으로 표현했지만...

• 실제로는 dp값을 바로 업데이트 하면 j반복문 내의 업데이트에 연쇄적으로 영향을 준다.
• 따라서 한 번 접근하면 이후에는 값이 변해도 상관없는 array에 값을 업데이트 한 후, 모든 array 값이 업데이트 되면 이 값을 dp에 복사해 주었다.