programmers) 정수 삼각형

 정수 삼각형, DFS로 접근했다가 DP로 다시 풀기

처음에는 삼각형의 꼭대기에서 시작해서 아래로 내려가며 모든 경로를 탐색하면 된다고 생각했다.
각 위치에서 아래 왼쪽 또는 아래 오른쪽으로 내려갈 수 있기 때문에, 자연스럽게 DFS처럼 모든 경우를 따라가보는 방식을 떠올렸다.

하지만 그렇게 접근하니 시간초과가 났다.

이 문제는 모든 경로를 직접 탐색하는 문제가 아니라, 각 위치까지 도달했을 때의 최대 합을 저장하면서 내려가는 DP 문제였다.

---

문제 정보

항목내용

문제	프로그래머스 정수 삼각형
레벨	Level 3
유형	DP (동적 계획법)
사용 언어	Java
첫 접근	DFS / 완전탐색
결과	시간초과
최종 접근	DP
핵심	각 칸까지 도달할 수 있는 최대 합 저장

문제 설명

삼각형 모양으로 숫자가 주어질 때, 맨 위에서 시작하여 아래층으로 내려가면서 숫자를 선택한다.

현재 위치에서 이동할 수 있는 곳은 바로 아래 또는 아래 오른쪽 칸뿐이다.

마지막 층까지 내려갔을 때 만들 수 있는 최대 합을 구하는 문제이다.

제한사항

• 삼각형의 높이는 1 이상 500 이하
• 삼각형을 이루는 숫자는 0 이상 9,999 이하의 정수

입출력 예시

입력

[
     [7],
    [3, 8],
   [8, 1, 0],
  [2, 7, 4, 4],
 [4, 5, 2, 6, 5]
]

출력

30

설명

7 → 3 → 8 → 7 → 5

위 경로를 선택하면 합이 30이 되어 최댓값이 된다.

---

처음 문제를 보고 떠올린 생각

정수 삼각형 문제는 꼭대기에서 시작해서 아래층으로 내려가며 숫자를 선택하고, 마지막 층까지 도착했을 때 만들 수 있는 최대 합을 구하는 문제다.

예를 들어 이런 구조라고 생각할 수 있다.

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

처음에는 각 위치에서 아래로 내려가는 선택지가 두 개라고 생각했다.

아래 왼쪽으로 내려가기
아래 오른쪽으로 내려가기

그래서 타겟 넘버 문제처럼 두 갈래로 계속 나뉘는 트리 구조를 떠올렸다.

7
├── 3
│   ├── 8
│   └── 1
└── 8
    ├── 1
    └── 0

이렇게 보면 모든 경로를 끝까지 내려가면서 합을 구하고, 그중 최댓값을 찾으면 될 것 같았다.

---

처음 작성한 풀이 방향

처음에는 대략 이런 식으로 생각했다.

1. 꼭대기 값에서 시작한다.
2. 다음 층으로 내려간다.
3. 왼쪽 아래, 오른쪽 아래 두 방향으로 재귀 호출한다.
4. 마지막 층에 도착하면 합을 비교해서 최댓값을 갱신한다.

그래서 DFS 방식으로 모든 경로를 탐색하려고 했다.

하지만 이 방식은 층이 깊어질수록 경우의 수가 너무 많아진다.

한 층 내려갈 때마다 선택지가 두 개씩 생기기 때문에, 단순 DFS로 모든 경로를 탐색하면 경우의 수가 빠르게 늘어난다.

1층: 1개
2층: 2개
3층: 4개
4층: 8개
...

즉, 높이가 커질수록 탐색해야 하는 경로가 폭발적으로 증가한다.

이것이 시간초과의 원인이었다.

 

시간초과가 나는 이유

각 위치에서는 아래 왼쪽 또는 아래 오른쪽으로 내려갈 수 있다.
즉, 한 층 내려갈 때마다 선택지가 2개씩 생긴다.

1층: 1개
2층: 2개
3층: 4개
4층: 8개
5층: 16개
...

삼각형의 높이를 h라고 하면 DFS로 탐색해야 하는 경로의 수는 대략 `2^(h-1)`개가 된다.

프로그래머스 정수 삼각형은 높이가 최대 500까지 가능하다.
따라서 모든 경로를 DFS로 탐색하면 최악의 경우 `2^499`개의 경로를 확인해야 한다.

이 정도의 경우의 수는 현실적으로 계산할 수 없기 때문에 시간초과가 난다.

처음에는 “두 갈래로 내려가니까 DFS로 풀 수 있겠다”고 생각했지만,
이 문제는 모든 경로를 직접 탐색하는 것이 아니라 각 칸까지 도달했을 때의 최대 합만 저장하면 되는 문제였다.

즉, 시간초과의 원인은 DFS 자체가 틀렸다기보다는
이 문제에서 DFS로 모든 경로를 직접 탐색하면 경우의 수가 너무 커진다는 점을 고려하지 못한 것이다.

---

왜 DFS로는 어려웠는가?

DFS로도 작은 입력은 풀 수 있다.
하지만 프로그래머스 정수 삼각형은 삼각형의 높이가 최대 500이기 때문에 모든 경로를 다 탐색하는 방식은 비효율적이다.

처음 접근에서 놓친 부분은 이것이었다.

같은 위치에 도착하는 경로가 여러 개 존재한다.

예를 들어 가운데 위치는 위쪽 두 칸에서 내려올 수 있다.

      3   8
       \ /
        1

1에 도착하는 방법은 두 가지다.

3에서 내려오는 경우
8에서 내려오는 경우

그런데 최종적으로 필요한 것은 모든 경로 자체가 아니라,

해당 위치까지 도달했을 때 만들 수 있는 최대 합이다.

따라서 1에 도착하는 모든 경로를 계속 따로 들고 갈 필요가 없다.
1에 도착할 수 있는 최대 합만 저장하면 된다.

이 점이 DFS와 DP의 차이였다.

---

DP로 다시 생각하기

DP로 접근하려면 먼저 dp의 의미를 정해야 한다.

이 문제에서는 입력 배열 triangle 자체를 DP 배열처럼 사용할 수 있다.

triangle[i][j] = i층 j번째 위치까지 도착했을 때의 최대 합

즉, 원래 triangle[i][j]에는 현재 칸의 숫자가 들어 있었지만,

계산을 진행하면서 그 값을 해당 칸까지 도착했을 때의 최대 누적합으로 바꾸는 것이다.

예를 들어 맨 위는 그대로 시작한다.

triangle[0][0] = 7

두 번째 층은 맨 위에서만 내려올 수 있다.

3까지 오는 최대 합 = 7 + 3 = 10
8까지 오는 최대 합 = 7 + 8 = 15

세 번째 층 가운데 값 1은 위쪽 두 칸 중 더 큰 값을 선택해야 한다.

      10   15
        \ /
         1

1까지 오는 최대 합 = max(10, 15) + 1 = 16

이렇게 각 칸에 도착할 수 있는 최대 합을 저장하면서 아래로 내려가면 된다.

---

위치별로 생각하기

정수 삼각형은 위치에 따라 위에서 올 수 있는 방향이 다르다.

위치올 수 있는 방향

맨 왼쪽	바로 위에서만 올 수 있음
맨 오른쪽	왼쪽 위에서만 올 수 있음
가운데	위쪽 두 칸 중 하나에서 올 수 있음

---

1. 맨 왼쪽

맨 왼쪽은 바로 위에서만 내려올 수 있다.

    7
   /
  3

그래서 이렇게 계산한다.

triangle[i][j] += triangle[i - 1][j];

---

2. 맨 오른쪽

맨 오른쪽은 왼쪽 위에서만 내려올 수 있다.

  7
   \
    8

그래서 이렇게 계산한다.

triangle[i][j] += triangle[i - 1][j - 1];

---

3. 가운데

가운데는 위쪽 두 칸에서 내려올 수 있다.

   10   15
     \ /
      1

더 큰 합을 만들어야 하므로 둘 중 큰 값을 선택한다.

triangle[i][j] += Math.max(triangle[i - 1][j - 1], triangle[i - 1][j]);

---

최종 코드

처음에는 DFS로 풀려고 해서 시간초과가 났지만, 다시 DP로 접근해서 아래와 같이 풀 수 있었다.

class Solution {
    public int solution(int[][] triangle) {
        
        for (int i = 1; i < triangle.length; i++) {
            for (int j = 0; j < triangle[i].length; j++) {
                if (j == 0) {
                    triangle[i][j] += triangle[i - 1][j];
                } else if (j == triangle[i].length - 1) {
                    triangle[i][j] += triangle[i - 1][j - 1];
                } else {
                    triangle[i][j] += Math.max(triangle[i - 1][j], triangle[i - 1][j - 1]);
                }
            }
        }

        int answer = 0;

        for (int value : triangle[triangle.length - 1]) {
            answer = Math.max(value, answer);
        }

        return answer;
    }
}

---

코드 흐름 정리

이 코드는 두 번째 층부터 마지막 층까지 내려가며 각 칸의 최대 누적합을 갱신한다.

for (int i = 1; i < triangle.length; i++)

i는 현재 층을 의미한다.

for (int j = 0; j < triangle[i].length; j++)

j는 현재 층에서의 위치를 의미한다.

즉, 이중 for문을 통해 삼각형의 모든 칸을 한 번씩 확인한다.

처음에는 for문을 사용했기 때문에 방향이 틀린 줄 알았는데,

정수 삼각형은 오히려 for문으로 푸는 DP 문제가 맞았다.

다만 중요한 것은 for문으로 모든 경로를 직접 탐색하는 것이 아니라,

for문으로 각 칸까지의 최대 합을 갱신해야 한다는 점이었다.

---

마지막 줄에서 최댓값 찾기

모든 층의 계산이 끝나면 마지막 줄에는 각 위치까지 도달했을 때의 최대 합이 들어 있다.

따라서 마지막 줄에서 가장 큰 값을 찾으면 된다.

int answer = 0;

for (int value : triangle[triangle.length - 1]) {
    answer = Math.max(value, answer);
}

예를 들어 마지막 줄이 이런 식으로 바뀌었다면:

[24, 25, 20, 27, 24]

정답은 그중 가장 큰 값인 27이다.

---

시간복잡도

이 풀이에서는 삼각형의 모든 칸을 한 번씩만 확인한다.

삼각형 안의 전체 숫자 개수를 N이라고 하면 시간복잡도는 다음과 같다.

O(N)

처음에 DFS로 모든 경로를 탐색하려고 했을 때는 경우의 수가 계속 늘어났지만,

DP로 풀면 각 칸을 한 번씩만 계산하면 된다.

---

공간복잡도

현재 코드는 별도의 DP 배열을 만들지 않고, 입력으로 받은 triangle 배열 자체를 갱신한다.

따라서 추가 공간복잡도는 다음과 같다.

O(1)

단, 이 방식은 원본 triangle 배열이 변경된다.

코딩테스트에서는 보통 문제가 되지 않지만, 원본 데이터를 보존해야 하는 상황이라면 별도의 dp 배열을 만들어야 한다.

---

처음 풀이와 최종 풀이 비교

구분처음 접근최종 접근

방식	DFS로 모든 경로 탐색	DP로 각 칸의 최대 합 저장
핵심 생각	모든 경우를 직접 내려가보자	각 위치까지의 최대 합만 저장하자
시간복잡도	매우 큼	O(N)
위치 관리	재귀에서 복잡해짐	이중 for문으로 명확함
결과	시간초과	통과 가능한 풀이

---

이번 문제에서 배운 점

이번 문제를 풀면서 가장 크게 배운 점은,

모든 경우의 수가 보인다고 해서 무조건 DFS로 끝까지 탐색해야 하는 것은 아니라는 것이다.

정수 삼각형도 처음에는 아래로 내려가는 경로가 두 갈래씩 나뉘기 때문에 DFS처럼 보였다.

하지만 이 문제는 모든 경로 자체가 필요한 것이 아니라,

각 위치까지 도달했을 때의 최대 합만 필요했다.

그래서 핵심은 다음과 같았다.

경로를 전부 저장하거나 탐색하지 않는다.
각 칸까지의 최대 합만 저장한다.

이것이 DP였다.

---

다시 풀 때 주의할 점

다시 풀 때는 아래 순서로 생각해야겠다.

순서확인할 것

1	모든 경로를 직접 탐색해야 하는 문제인지 확인한다
2	같은 위치에 여러 경로로 도착할 수 있는지 확인한다
3	해당 위치까지의 최댓값만 저장해도 되는지 생각한다
4	dp[i][j]의 의미를 정한다
5	맨 왼쪽, 맨 오른쪽, 가운데를 나누어 처리한다
6	마지막 줄에서 최댓값을 찾는다

---

마무리

처음에는 정수 삼각형을 DFS로 풀려고 했다.
아래로 내려갈 때마다 두 방향으로 나뉘기 때문에 모든 경로를 탐색하면 될 것 같았다.

하지만 그렇게 하면 경우의 수가 너무 많아져 시간초과가 난다.

다시 풀면서 이 문제는 각 칸까지의 최대 합을 저장하는 DP 문제라는 것을 이해했다.

DFS처럼 모든 경로를 직접 내려가지 않는다.
DP로 각 칸까지 도달할 수 있는 최대 합을 저장한다.

이번 문제를 통해 DP에서 중요한 것은 dp[i] 또는 dp[i][j]의 의미를 먼저 정하는 것이라는 점을 다시 느꼈다.

정수 삼각형에서는 그 의미가 다음과 같았다.

triangle[i][j] = i층 j번째 위치까지 도착했을 때의 최대 합

앞으로 DP 문제를 풀 때는 먼저 모든 경우를 직접 탐색하려고 하기보다,

중복되는 계산이 있는지, 이전 값으로 현재 값을 만들 수 있는지부터 확인해야겠다.