실전 문제 : ENCHANT (K모 회사)

📌 1. 문제 정의

무기 강화 주문서를 사용하여 집행검을 강화하는 시스템이 있다.

• 강화는 한 번에 +1, +2, +3 중 하나만 적용 가능하다.
• +0 레벨부터 시작해서 목표 레벨 +N까지 도달하는 모든 경우의 수를 구해야 한다.

🎯 예시:
N = 4일 때
가능한 경로:
+1 +1 +1 +1
+1 +3
+2 +2
등등...

---

💡 2. 해결 전략

이 문제는 동적 계획법(Dynamic Programming, DP)을 통해 해결할 수 있다.

🎯 접근 아이디어

• 현재 강화 레벨을 num이라 할 때,
  다음 강화는 num + 1, num + 2, num + 3 중 하나로 진행 가능.
• 따라서 Enchant(num) = Enchant(num + 1) + Enchant(num + 2) + Enchant(num + 3)
  👉 이게 이 문제의 점화식!

---

📦 3. 코드 분석

📍 전역 변수 및 캐시 초기화

int N;             // 목표 강화 레벨
int cache[100];    // 메모이제이션 캐시 (최대 N은 100 미만)

• N은 목표 강화 레벨
• cache[i]: i 레벨에서 시작해 N에 도달하는 경우의 수를 저장

---

📍 Enchant 함수 구현

int Enchant(int num)
{
    // 🎯 기저 사례
    if (num > N) return 0;      // 목표 초과: 실패
    if (num == N) return 1;     // 정확히 도달: 성공

    // 💾 캐시 확인
    int& ret = cache[num];
    if (ret != -1) return ret;  // 이미 계산된 값 반환

    // ✅ 점화식 적용
    return ret = Enchant(num + 1) + Enchant(num + 2) + Enchant(num + 3);
}

💬 num이 현재 강화 레벨일 때, 다음 레벨로 갈 수 있는 모든 경로를 탐색해 그 합을 반환한다.

---

📍 메인 함수

int main()
{
    N = 9;  // 예시: +9 집행검이 뜨는 경우의 수를 구하라

    memset(cache, -1, sizeof(cache));  // 캐시를 -1로 초기화

    int ret = Enchant(0);  // +0에서 시작
    cout << ret << endl;   // 결과 출력
}

• Enchant(0)부터 시작해서 +N까지 가는 경우의 수 계산
• memset으로 캐시 초기화 안 하면 쓰레기값이 남아 오류 발생 가능!

---

🧮 4. 실행 흐름 시뮬레이션 (N = 4)

Enchant(0) = Enchant(1) + Enchant(2) + Enchant(3)
Enchant(1) = Enchant(2) + Enchant(3) + Enchant(4)
Enchant(2) = Enchant(3) + Enchant(4) + Enchant(5)
...

✅ Enchant(4) = 1 (정확히 도달)
⛔ Enchant(5) > N → 0 반환

---

🔍 5. 예시 결과

N = 4

가능한 경로:

• +1 +1 +1 +1
• +1 +2 +1
• +2 +2
• +1 +3
• +3 +1
  ...

출력: 7 (총 7가지 경로)

N = 9

🎲 모든 경로의 경우의 수를 효율적으로 계산 → 출력: 149

---