[C++] 백준/Gold/2011. 암호코드

문제: 암호 코드 (백준 2011번)

문제 분석

• 주어진 숫자 문자열을 알파벳으로 변환하는 경우의 수를 찾는 문제.
• '1' ~ '26'까지의 숫자는 각각 'A' ~ 'Z'로 변환 가능.
• '0'은 단독으로 존재할 수 없으며, 반드시 앞 숫자와 조합되어야 한다.

---

풀이: 동적 계획법 (DP)

1. DP 배열 정의

• dp[i] = 주어진 숫자에서 i번째 숫자까지 해석할 수 있는 방법의 수
• 핵심은 한 자리, 두 자리씩 해석하는 경우를 고려하는 것이다.

2. 점화식

• 1자리 숫자로 해석 가능한 경우 (num[i-1] ≠ '0')
  • → dp[i] += dp[i-1]
• 2자리 숫자로 해석 가능한 경우 (10 ≤ 두 자리 숫자 ≤ 26)
  • → dp[i] += dp[i-2]
• MOD 연산 적용: dp[i] %= 1000000
  • 문제에서 요구하는 값이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 저장한다.

---

코드 설명

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    string num; cin >> num;

    if (num[0] == '0') // 첫 번째 자리가 0이면 해석 불가
    {
        cout << 0;
        return 0;
    }

    int n = num.size();
    vector<int> dp(n + 1);
    dp[0] = 1; // 아무것도 해석하지 않은 경우 (기본값)
    dp[1] = 1; // 첫 번째 숫자는 한 가지 방법으로 해석 가능

    for (int i = 2; i <= n; i++)
    {
        int oneDigit = num[i - 1] - '0';       // 현재 한 자리 숫자
        int twoDigit = stoi(num.substr(i - 2, 2)); // 현재 두 자리 숫자

        if (oneDigit > 0) // 1~9 범위일 때
            dp[i] = (dp[i] + dp[i - 1]) % 1000000;

        if (10 <= twoDigit && twoDigit <= 26) // 10~26 범위일 때
            dp[i] = (dp[i] + dp[i - 2]) % 1000000;
    }

    cout << dp[n];
}