[백준]1932번: 정수 삼각형

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

1932번: 정수 삼각형

---

너무너무 dp 문제다

 

간단하게 문제 예제로 생각해보면 쉽게 이해가 간다

경로합을 저장할 배열을 따로 만들어서 한 층씩 저장한다고 생각해보자.

1층은 당연히 그대로 7일 것이고,

2층은 각각 7+3=10, 7+8=15가 된다

 

---

3층

0번째 칸: 10이 그대로 내려와서 10+8=18

1번째 칸: (10,15중 큰 값) + 1 = 15+1 = 16

2번째 칸: 15가 그대로 내려와서 15+0=15

 

---

4층

0번째 칸: 18이 그대로 내려와서 18+2=20

1번째 칸: (18,16중 큰 값) + 7 = 18+7=25

2번째 칸: (16,15중 큰 값) + 4 = 16+4=20

3번째 칸: 15가 그대로 내려와서 15+4=19

---

5층

0번째 칸: 20이 그대로 내려와서 20+4=24

1번째 칸: (20,25중 큰 값)+5 = 25+5 = 30

2번째 칸: (25,20중 큰 값)+2 = 25+2 = 27

3번째 칸: (20,19중 큰 값)+6 = 20+6 = 26

4번째 칸: 19가 그대로 내려와서 19+5=24

---

정리해보면,

• 각 층에서 첫번째칸과 마지막칸은 바로 위의 숫자를 선택하여 더해준다.
• 중간 칸들은 자신의 대각선 왼쪽, 대각선 오른쪽 중 숫자가 더 큰 것을 선택하여 더해준다.

 

삼각형 리스트를 triangle, 경로합 리스트를 dp라고 할 때 위 규칙을 식으로 나타내면

if j==0:
  dp[i][j] = dp[i-1][j] + triangle[i][j]
elif j==i:
  dp[i][j] = dp[i-1][j-1] + triangle[i][j]
else:
  dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

이정도로 적을 수 있겠다.

---

정답 코드

import sys 
input = sys.stdin.readline

n = int(input())

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

dp=[[0]*n for _ in range(n)]
dp[0][0]=triangle[0][0] #1층 초기화
for i in range(1,n): #2층부터 채우기
  for j in range(i+1):
    if j==0:
      dp[i][j]=dp[i-1][j]+triangle[i][j]
    elif j==i:
      dp[i][j]=dp[i-1][j-1]+triangle[i][j]
    else:
      dp[i][j]=max(dp[i-1][j-1]+triangle[i][j], dp[i-1][j]+triangle[i][j])

print(max(dp[n-1])) #마지막층의 최댓값을 출력