샘플 문제 : TRIANGLE_PATH

1. 🔍 문제 정의: Triangle Path란?

• 숫자로 구성된 삼각형에서 맨 위 (0,0) 지점에서 시작해 아래 또는 아래 오른쪽으로만 이동하며
• 만나는 숫자를 모두 합산할 때,
  ➤ 합이 최대가 되는 경로의 값을 구하라.

---

2. 📌 입력 예시

6
1 2
3 7 4
9 4 1 7
2 7 5 9 4

• 경로 예시: 6 → 7 → 1 → 7 → 4 → 총합 = 25
• 최적 경로: 6 → 7 → 4 → 7 → 9 → 총합 = 33

---

3. 💡 핵심 아이디어: 동적 계획법(DP)

✅ 핵심 점화식

path(y, x) = board[y][x] + max(path(y+1, x), path(y+1, x+1))

• 현재 위치에서 아래 또는 대각선 오른쪽 아래 중 더 큰 값을 선택하여 이동
• 재귀 + 메모이제이션으로 중복 계산 방지

✅ 기저 사례

if (y == N) return 0;

• 삼각형을 벗어났을 경우 종료

---

4. 🧠 알고리즘 흐름 요약

1. board[y][x]에 현재 위치 값 저장
2. 아래쪽 경로(y+1, x)와 오른쪽 대각선 경로(y+1, x+1) 비교
3. 더 큰 쪽을 선택하고 합산
4. 결과를 cache[y][x]에 저장해 중복 계산 방지
5. nextX[y][x]에 다음 위치 저장하여 경로 추적

---

5. 🧪 전체 코드 구현 및 분석

📄 전체 코드

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<vector<int>> board;      // 입력 삼각형
vector<vector<int>> cache;      // DP 캐시
vector<vector<int>> nextX;      // 경로 추적용

int path(int y, int x)
{
    if (y == N) return 0;

    int& ret = cache[y][x];
    if (ret != -1) return ret;

    int left = path(y + 1, x);
    int right = path(y + 1, x + 1);

    // 경로 저장
    nextX[y][x] = (left > right) ? x : x + 1;

    return ret = board[y][x] + max(left, right);
}

int main()
{
    board = {
        {6},
        {1, 2},
        {3, 7, 4},
        {9, 4, 1, 7},
        {2, 7, 5, 9, 4}
    };

    N = board.size();
    cache = vector<vector<int>>(N, vector<int>(N, -1));
    nextX = vector<vector<int>>(N, vector<int>(N));

    int ret = path(0, 0);
    cout << "최대 경로 합: " << ret << "\n";

    // 경로 출력
    cout << "경로: ";
    int y = 0, x = 0;
    while (y < N)
    {
        cout << board[y][x];
        if (y != N - 1) cout << " → ";
        x = nextX[y][x];
        y++;
    }
}

---

6. 🔎 코드 라인별 분석

🔹 board, cache, nextX

• board: 삼각형 숫자 배열
• cache: 위치별 최대 합 저장 (-1이면 아직 계산 X)
• nextX: 다음 경로 방향 저장

🔹 path(y, x)

• 재귀 함수로 현재 위치부터의 최대 합 계산
• 캐시 값을 먼저 확인해서 계산 결과 재활용
• 아래와 대각선 아래를 비교해서 큰 값 선택
• nextX를 통해 다음 이동 위치 기억

🔹 main()

• board 초기화
• path(0,0) 호출로 최대 경로 합 계산
• while문으로 nextX 따라가며 경로 출력

---

7. ✅ 실행 결과

최대 경로 합: 33
경로: 6 → 7 → 4 → 7 → 9

---