백준 9184 - 신나는 함수 실행

1️⃣ 문제 접근

이 문제는 함수 w(a, b, c)를 정의하고 값을 구하는 문제이다.
처음 보면 단순 재귀처럼 보이지만, 중복 계산이 매우 많은 구조이다.

👉 따라서 핵심은
DP(동적 계획법) + 메모이제이션이다.

---

2️⃣ 처음 시도 (삽질 포인트 😇)

처음에는 다음과 같은 실수를 했다:

• vector<vector<vector<int>>> w[20][20][20];
  → ❌ 배열 + 벡터를 섞어서 타입이 꼬임

• a == b == c == 20
  → ❌ C++에서 체인 비교 안됨

• 3중 for문을 함수 안에 넣어서 매번 계산
  → ❌ DP 의미 사라짐 (비효율)

👉 이 단계에서 느낀 점:

“DP는 계산을 한 번만 해야 의미가 있다”

---

3️⃣ 핵심 아이디어

이 문제의 핵심 조건은 3가지다:

if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return w[20][20][20];

그리고 점화식:

if (a < b && b < c)
    w[a][b][c] = w[a][b][c-1] + w[a][b-1][c-1] - w[a][b-1][c];
else
    w[a][b][c] = w[a-1][b][c] + w[a-1][b-1][c] + w[a-1][b][c-1] - w[a-1][b-1][c-1];

👉 중요한 점:

• 현재 값은 항상 이전 상태들로부터 계산됨
• 따라서 작은 값부터 채워야 한다

---

4️⃣ 해결 전략

✔ Step 1: DP 테이블 정의

int w[21][21][21];

👉 0 ~ 20까지 사용해야 하므로 21 크기

---

✔ Step 2: 미리 값 계산 (init)

void init(){
    for (int i = 0; i <= 20; i++) {
        for (int j = 0; j <= 20; j++) {
            for (int k = 0; k <= 20; k++) {
                if (i == 0 || j == 0 || k == 0)
                    w[i][j][k] = 1;
                else if (i < j && j < k)
                    w[i][j][k] = w[i][j][k-1] + w[i][j-1][k-1] - w[i][j-1][k];
                else
                    w[i][j][k] = w[i-1][j][k] + w[i-1][j-1][k] + w[i-1][j][k-1] - w[i-1][j-1][k-1];
            }
        }
    }
}

👉 핵심: 오름차순으로 채워야 함

---

✔ Step 3: 값 조회 함수

int fun(int a, int b, int c){
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (a > 20 || b > 20 || c > 20) return w[20][20][20];
    return w[a][b][c];
}

👉 계산은 이미 끝났기 때문에 조회만 수행

---

✔ Step 4: 메인에서 사용

init();

while(true){
    cin >> a >> b >> c;
    if(a == -1 && b == -1 && c == -1) break;
    cout << "w(" << a << ", " << b << ", " << c << ") = " << fun(a,b,c) << '\n';
}

---

5️⃣ 시간복잡도

• DP 초기화:
  👉 21^3 = 9261 → 매우 작음

• 각 쿼리:
  👉 O(1)

---

6️⃣ 깨달은 점 💡

• DP는 “계산”과 “조회”를 분리하는 것이 중요하다
• 재귀 문제도 반복문으로 풀 수 있지만
  👉 의존성 순서를 직접 설계해야 한다
• 작은 상태 → 큰 상태 순으로 채워야 안전하다

---