[Python] 1932번 정수 삼각형

✏️ 문제

 

문제 파악

입력으로 주는 배열을 기준으로 합을 담은 dp 배열의 값을 구하면 다음과 같이 나온다.

중요한 것은 그림의 빨간 부분과 같이 중간에 겹치는 부분이 생기는데 이때문에 경우를 나눠서 구해야 한다.

• dp[n][0]
• dp[n][1] ~ dp[n][n-1] : 어짜피 최대값을 구하므로 max 값만 두면 된다.
• dp[n][n]

 

 

알고리즘

• 다이나믹 프로그래밍 

 

 

코드

n = int(input())
ary = [list(map(int, input().split())) for _ in range(n)] 
dp = [[0] * (n+1) for _ in range(n)]
dp[0][0] = ary[0][0]

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

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