문제

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

---

풀이

🔎 삼각형을 어떻게 저장할까?

입력으로 주어지는 삼각형은 아래와 같다.

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

이걸 2차원 리스트로 저장해 두자.

예: tri[i][j] = i번째 줄, j번째 숫자
(인덱스는 0부터로 할지, 1부터로 할지는 너가 편한 대로!)

🔁 “지나온 경로의 최대 합”을 같이 저장하자

단순히 숫자만 저장해 두면 안 되고,
그 자리에 도착했을 때 만들 수 있는 최대 합을 같이 기억해야 한다.

dp[i][j] = 삼각형 위에서 시작해서 (i, j)에 도착했을 때의 최대 합

단, 맨 윗줄은 시작점이니까:
dp[0][0] = tri[0][0] (또는 1부터 시작했다면 dp[1][1] = tri[1][1])

⬇️ 바로 위에서만 내려올 수 있다!

(i, j) 위치로 올 수 있는 경우는 최대 두 가지다.

바로 왼쪽 위에서 내려오는 경우
→ (i-1, j-1) → (i, j)

바로 오른쪽 위에서 내려오는 경우
→ (i-1, j) → (i, j)

그래서 점화식(규칙)은 이렇게 생긴 형태가 된다

양쪽 중간에 있는 칸들에 대해서
$dp[i][j] = tri[i][j] + max(dp[i-1][j-1], dp[i-1][j])$

⚠️ 양 끝(맨 왼쪽, 맨 오른쪽)은 예외 처리

맨 왼쪽 칸은 왼쪽 위가 없음
→ (i-1, j) 에서만 올 수 있음

맨 오른쪽 칸은 위가 없음 (정확히는 (i-1, j)가 없음)
→ (i-1, j-1) 에서만 올 수 있음

즉,
맨 왼쪽: dp[i][0] = dp[i-1][0] + tri[i][0]

맨 오른쪽: dp[i][i] = dp[i-1][i-1] + tri[i][i] (0-index 기준일 때, j==i)

🎯 정답은 어디에 있을까?

마지막 줄에 도착했을 때의 값들 중에서 최댓값이 답이다.

answer = max(dp[n-1])

---

코드

아래는 위 로직을 구현한 최종 코드이다.

n = int(input())
tri = []
dp = [[0 for j in range(i+1)] for i in range(n)]

for i in range(n):
    tri.append(list(map(int, input().split())))

dp[0][0] = tri[0][0]

for i in range(1, n):
    for j in range(i+1):

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

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

---

마무리

이 문제는 DP의 기본 원칙인
“큰 문제를 작은 문제의 조합으로 해결한다”
는 개념을 잘 보여준다.

현재 위치의 최댓값은
➜ “위에서 내려올 수 있는 최댓값” + “현재 값”

중간, 왼쪽 끝, 오른쪽 끝이 분기 처리 포인트

구조를 한 번 이해하면 비슷한 유형을 훨씬 빠르게 풀 수 있다!