[백준] 1932번 정수 삼각형

💡문제접근

• 삼각형의 빗변 상에 위치한 값은 한 칸 위에 있는 값을 그대로 더해주면 된다. 하지만 안쪽에 있는 값은 왼쪽 대각선 위의 숫자와 오른쪽 대각선 위의 숫자와 비교해 값을 넣으면 된다.

💡코드(메모리 : 35712KB, 시간 : 152ms)

import sys
input = sys.stdin.readline

n = int(input().strip())
dp = []
for i in range(n):
    dp.append(list(map(int, input().strip().split())))

for i in range(1, n):
    for j in range(len(dp[i])):
        # 왼쪽 빗변 상에 위치하는 값의 경우
        if j == 0:
            dp[i][j] = dp[i-1][j] + dp[i][j]
        # 왼쪽 빗변과 오른쪽 빗변 사이 가운데 쪽에 위치하는 값의 경우
        elif 0 < j < len(dp[i]) - 1:
            dp[i][j] = max(dp[i-1][j-1] + dp[i][j], dp[i-1][j] + dp[i][j])
        # 오른쪽 빗변 상에 위치하는 값의 경우
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i][j]
print(max(dp[-1]))

💡접근방법

	i = 0							7
	i = 1		         		3	   8
	i = 2			  		 8      1     0 
	i = 3				  2     7      4     4
	i = 4			   4     5      2     6    5 

• i = 1층

  • dp[1][0] = dp[1][0] + dp[0][[0]
  • dp[1][1] = dp[1][1] + dp[0][0]

• i = 2층

  • dp[2][0] = dp[1][0] + dp[2][0]
  • dp[2][1] = max(dp[1][0] + dp[2][1], dp[1][1] + dp[2][1])
  • dp[2][2] = dp[1][1] + dp[2][2]

---

• 위의 2층을 기준으로 점화식을 세워보면 다음과 같다.

①. 왼쪽 빗변에 위치하는 경우

dp[i][j] = dp[i-1][j] + dp[i][j]

②. 가운데에 위치하는 경우

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

③. 오른쪽 빗변에 위치하는 경우

dp[i][j] = dp[i-1][j-1] + dp[i][j]

💡소요시간 : 10m