[프로그래머스 Lv.3] 정수 삼각형(Java) - DP 두 방향 비교

📌 핵심 요약

• 위→아래 — "꼭대기에서 여기까지"의 최대 합. 부모를 참조하므로 양 끝 경계 분기 2개가 필요하고, 마지막에 바닥 행을 훑어야 한다.
• 아래→위 — "여기서 바닥까지"의 최대 합. 자식을 참조하는데 아랫 행이 항상 한 칸 넓으므로 경계 분기가 아예 없다. dp[0][0]이 곧 정답이다.

 

목차

프로그래머스 #43105

정수 삼각형

높이 ≤ 500 · 원소 0 ~ 9,999

난이도: [Level 3]

숫자가 적힌 삼각형이 주어진다. 꼭대기에서 출발해 아래로 내려가되, 한 칸 이동할 때는 바로 아래 또는 바로 아래 오른쪽 칸으로만 갈 수 있다. 바닥까지 내려가면서 거쳐간 숫자의 합이 최대가 되도록 할 때, 그 합을 구하면 된다.

풀이 과정

1. 경로 수와 칸 수를 비교해 DP로 접근할지 판단한다.
2. DP 배열 한 칸에 담을 값의 의미를 한 문장으로 확정한다.
3. 그 문장에 맞춰 점화식을 세우고 경계를 확인한다.
4. 정답이 어느 칸에 남는지 확인하고 반환한다.

1 규모를 먼저 확인했다

삼각형 높이는 최대 500이다. 완전탐색으로 모든 경로를 세어보면 어떻게 되는지부터 계산했다.

접근	연산 횟수	판정
모든 경로 완전탐색	칸마다 2갈래 → 2⁴⁹⁹	불가능
칸마다 한 번씩만 계산	1+2+…+500 = 125,250	여유

경로 수는 폭발하는데 칸 수는 12만 개뿐이다. 이 격차가 곧 서로 다른 경로들이 같은 칸을 수없이 중복해서 지나간다는 뜻이므로, 칸마다 결과를 한 번만 계산해 재사용하면 된다고 판단했다.

2 DP 배열에 무엇을 담을 것인가

DP에서 가장 먼저 결정할 것은 "배열 한 칸에 무엇을 담는가"다. 이것을 한 문장으로 쓰지 못하면 점화식도 세울 수 없다.

그리고 이 문제는 그 문장을 두 가지로 쓸 수 있다. 어느 쪽을 고르느냐에 따라 코드가 완전히 달라진다.

방향	dp[r][c]의 의미	참조 대상
위 → 아래	꼭대기에서 출발해 (r,c)까지 도달하는 최대 합	부모 (윗 행)
아래 → 위	(r,c)에서 출발해 바닥까지 내려가는 최대 합	자식 (아랫 행)

⚠️

방향을 먼저 못박아야 하는 이유

같은 dp[2][1]이라도 위→아래에서는 16, 아래→위에서는 13이 들어간다. 둘 다 맞는 값이지만 뜻이 다르다. 방향을 정하지 않고 점화식부터 쓰면 두 의미가 섞인다.

3 방법 1: 위에서 아래로

구하려는 값과 변수 정의

dp[r][c]는 꼭대기에서 출발해 (r행, c열) 칸까지 도달하는 경로들 중, 거쳐간 숫자 합의 최댓값이다.

• r — 행 번호. 꼭대기가 0행이고 아래로 갈수록 증가한다
• c — 그 행 안에서의 열 번호. r행은 칸이 r+1개이므로 c는 0부터 r까지다
• triangle[r][c] — 그 칸에 원래 적혀 있는 숫자
• 기준점 — dp[0][0] = triangle[0][0]. 꼭대기는 출발점이므로 자기 숫자 그대로다

식을 한국어 문장으로 옮기면

식은 다음과 같다.

   

점화식 — 위에서 아래로

dp[r][c] = triangle[r][c] + max(dp[r-1][c-1], dp[r-1][c])

문장으로 번역하면 이렇다.

ℹ️

식의 의미

"(r,c)까지의 최대 합은, 나에게 올 수 있는 두 부모 칸 중 더 큰 쪽의 값에 내 칸 숫자를 더한 것이다."

왜 부모가 [r-1][c-1]과 [r-1][c]인가

문제에 적힌 "바로 아래 또는 바로 아래 오른쪽"은 자식 방향 설명이다. 지금 필요한 것은 반대인 부모 방향이므로 뒤집어야 한다. (r-1, c)에서 출발한다고 놓고 자식을 따져보았다.

(r-1, c)에서의 이동	도착 칸
바로 아래	(r, c)
바로 아래 오른쪽	(r, c+1)

이 표를 거꾸로 읽으면 "(r, c)에 도착하려면 어디서 왔어야 하는가"가 나온다.

(r, c)에 도착한 경로	출발 칸
바로 아래로 내려온 경우	(r-1, c)
바로 아래 오른쪽으로 내려온 경우	(r-1, c-1)

두 번째 줄에서 열 번호가 줄어드는 이유는, 오른쪽으로 한 칸 이동해서 c에 도착했다면 출발점은 c보다 하나 작은 c-1이었어야 하기 때문이다. 이 지점이 헷갈리기 쉬워 손으로 한 번 그려서 확인했다.

경계 — 부모가 하나뿐인 칸

각 행의 양 끝은 부모가 하나밖에 없다.

위치	조건	없는 부모	이유
왼쪽 끝	c == 0	dp[r-1][-1]	열 번호가 음수
오른쪽 끝	c == r	dp[r-1][r]	r-1행은 칸이 r개(0~r-1)뿐
중간	그 외	없음	둘 다 존재

즉 삼각형의 두 빗변은 각각 한 가지 경로로만 도달 가능하다. 왼쪽 빗변은 계속 왼쪽 아래로만, 오른쪽 빗변은 계속 오른쪽 아래로만 내려온 경로다.

코드

   

Java — 위에서 아래로

class Solution {
    public int solution(int[][] triangle) {
        int n = triangle.length;

        // 행마다 길이가 다른 삼각형 배열
        int[][] dp = new int[n][];
        for (int r = 0; r < n; r++) {
            dp[r] = new int[r + 1];
        }

        dp[0][0] = triangle[0][0];

        for (int r = 1; r < n; r++) {
            for (int c = 0; c <= r; c++) {
                if (c == 0) {
                    // 왼쪽 끝 — 부모가 하나
                    dp[r][c] = triangle[r][c] + dp[r-1][c];
                } else if (c == r) {
                    // 오른쪽 끝 — 부모가 하나
                    dp[r][c] = triangle[r][c] + dp[r-1][c-1];
                } else {
                    // 중간 — 부모 둘 중 큰 쪽
                    dp[r][c] = triangle[r][c]
                                 + Math.max(dp[r-1][c-1], dp[r-1][c]);
                }
            }
        }

        // 바닥의 어느 칸으로 내려가도 되므로 마지막 행 전체를 훑는다
        int answer = 0;
        for (int c = 0; c < n; c++) {
            answer = Math.max(answer, dp[n-1][c]);
        }

        return answer;
    }
}

⚠️

정답은 특정 칸 하나가 아니다

바닥의 어느 칸으로 내려가도 되므로 마지막 행 전체의 최댓값이 정답이다. dp[n-1][0]이나 dp[n-1][n-1] 같은 특정 칸이 아니다.

추적

예시 삼각형으로 확인했다.

   

입력 — 예시 삼각형

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

0행 — 기준점이므로 dp[0][0] = 7이다.

1행 — c=0이 왼쪽 끝, c=1은 r과 같으므로 오른쪽 끝이다. 둘 다 경계다.

c	계산	dp
0	3 + dp[0][0]=7	10
1	8 + dp[0][0]=7	15

2행 — c=1이 처음으로 부모가 둘인 칸이다.

c	계산	dp
0	8 + dp[1][0]=10	18
1	1 + max(10, 15) = 1+15	16
2	0 + dp[1][1]=15	15

3행

c	계산	dp
0	2 + 18	20
1	7 + max(18, 16) = 7+18	25
2	4 + max(16, 15) = 4+16	20
3	4 + 15	19

4행

c	계산	dp
0	4 + 20	24
1	5 + max(20, 25) = 5+25	30
2	2 + max(25, 20) = 2+25	27
3	6 + max(20, 19) = 6+20	26
4	5 + 19	24

마지막 행의 최댓값 30. 예시 답과 일치한다.

4 방법 2: 아래에서 위로

의미를 뒤집으면 경계가 사라진다

이번에는 dp[r][c]를 (r,c)에서 출발해 바닥까지 내려가는 경로들 중 최대 합으로 정의했다. 그러면 참조 대상이 부모가 아니라 자식이 된다.

   

점화식 — 아래에서 위로

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

문장으로 번역하면 "(i,j)에서 바닥까지의 최대 합은, 내려갈 수 있는 두 자식 칸 중 더 큰 쪽의 값에 내 칸 숫자를 더한 것이다."

여기서 결정적인 차이가 나온다. 두 방향의 경계 상황을 나란히 놓고 비교했다.

위→아래에서 c 위치	부모 [r-1][c-1]	부모 [r-1][c]
c = 0	인덱스 -1	존재
c = r	존재	범위 초과
중간	존재	존재

아래→위에서 j 위치	자식 [i+1][j]	자식 [i+1][j+1]
j = 0	존재	존재
j = i	존재	존재
중간	존재	존재

전부 존재한다. 이유는 삼각형의 형태 자체에 있다. i행은 i+1칸이고 i+1행은 i+2칸이다. j가 최대 i까지 갈 때 j+1은 최대 i+1인데, 아래 행의 마지막 인덱스가 정확히 i+1이다.

💡

아랫 행이 항상 한 칸 더 넓다

그래서 자식은 절대 배열 밖으로 나갈 수 없다. 경계 분기 두 개가 통째로 사라지는 이유다.

코드

   

Java — 아래에서 위로

class Solution {
    public int solution(int[][] triangle) {
        int height = triangle.length;

        int[][] dp = new int[height][];
        for (int i = 0; i < height; i++) {
            dp[i] = new int[i + 1];
        }

        // 바닥은 그 자체가 "여기서 바닥까지"의 값이다
        for (int j = 0; j < height; j++) {
            dp[height-1][j] = triangle[height-1][j];
        }

        // 밑에서 두 번째 줄부터 위로 올라간다
        for (int i = height - 2; i >= 0; i--) {
            for (int j = 0; j < dp[i].length; j++) {
                dp[i][j] = triangle[i][j]
                           + Math.max(dp[i+1][j], dp[i+1][j+1]);
            }
        }

        // 꼭대기에 남은 값이 곧 정답이다
        return dp[0][0];
    }
}

반복 조건을 j < dp[i].length로 쓴 이유가 있다. 삼각형 모양으로 배열을 잡아두었기 때문에 배열 자신이 범위 정보를 들고 있다. j <= i와 결과는 같지만, 앞의 것은 "배열이 가진 만큼 돈다"이고 뒤의 것은 "내가 계산한 범위만큼 돈다"라는 차이가 있다.

추적

같은 예시로 아래에서 올라가 보았다.

i = 3 (자식은 4행 [4,5,2,6,5])

j	원래값	max(자식)	결과
0	2	max(4, 5) = 5	7
1	7	max(5, 2) = 5	12
2	4	max(2, 6) = 6	10
3	4	max(6, 5) = 6	10

i = 2 (자식은 [7,12,10,10])

j	원래값	max(자식)	결과
0	8	max(7, 12) = 12	20
1	1	max(12, 10) = 12	13
2	0	max(10, 10) = 10	10

i = 1 (자식은 [20,13,10])

j	원래값	max(자식)	결과
0	3	max(20, 13) = 20	23
1	8	max(13, 10) = 13	21

i = 0 (자식은 [23,21])

j	원래값	max(자식)	결과
0	7	max(23, 21) = 23	30

dp[0][0] = 30으로 일치한다. 여기서 주목할 점은 중간값들이 위→아래 버전과 전혀 다르다는 것이다. i=2에서 나온 20, 13, 10은 "꼭대기에서 여기까지"가 아니라 "여기서 바닥까지"의 최댓값이다. 방향이 바뀌면서 dp의 의미 자체가 뒤집혔다.

원본 배열을 직접 수정하는 변형

이 방향에서는 dp 배열을 따로 만들지 않고 triangle에 바로 누적하는 코드를 자주 본다. 메모리를 아끼는 기법이지만 대가가 있어 정리해 두었다.

구분	triangle 직접 수정	별도 dp 배열
추가 메모리	없음	O(n²)
원본 데이터	파괴됨	보존됨
디버깅	원본과 대조 불가	나란히 비교 가능
재호출	두 번째부터 오답	항상 동일 결과

재호출 항목이 실질적인 위험이다. 같은 배열 참조로 solution을 두 번 호출하면 첫 호출이 이미 값을 덮어썼기 때문에 두 번째는 엉뚱한 답이 나온다. 채점 환경에서는 매번 새 배열이 주어지므로 통과하지만, 일반적인 코드에서는 "인자로 받은 것은 건드리지 않는다"를 기본값으로 두는 편이 낫다고 판단했다.

5 두 방향 비교

구분	위 → 아래	아래 → 위
dp 의미	꼭대기 → 여기까지 최대 합	여기 → 바닥까지 최대 합
참조 대상	부모 (윗 행)	자식 (아랫 행)
경계 분기	2개 필요	없음
마지막 단계	바닥 행 훑어 최댓값	dp[0][0]이 곧 정답
사고 방향	직관과 일치	거꾸로 생각해야 함
시간 복잡도	O(n²)	O(n²)

코드 관점에서는 아래→위가 확실히 우세하다. 경계 분기 2개와 마지막 최댓값 루프가 통째로 사라진다. 다만 "출발점에서 쌓아간다"는 직관과 반대 방향이므로, 처음 익힐 때는 위→아래로 확실히 잡아둔 뒤 넘어가는 편이 낫다고 판단했다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.