[백준] 2011번

💻 C++ 기반

암호코드
https://www.acmicpc.net/problem/2011

✔️ 0은 암호 해석이 불가능하다.
✔️ 01은 1이라고 보면 안된다.
✔️ 10은 10이라고 본다.
✔️ 참고로 문제 설명이 모호하다는 의견이 다분하다.

1. 테이블 정의하기
dp[i]: 암호의 i번째 자리까지 나올 수 있는 해석의 가짓수

2. 점화식 찾기
예를 들어, 11111이라는 암호가 들어왔다고 하자.

dp[1] = 1
1

dp[2] = 2
1, 1
11

dp[3] = 3
1, 1, 1
11, 1
1, 11

dp[4] = 5
1, 1, 1, 1
11, 1, 1
1, 11, 1
1, 1, 11
11, 11

dp[5] = 8
1, 1, 1, 1, 1
11, 1, 1, 1
1, 11, 1, 1
1, 1, 11, 1
1, 1, 1, 11
11, 11, 1
1, 11, 11
11, 1, 11

규칙을 찾을 수 있다.
1. k자리 암호 해석문은 k-1자리 암호 해석문의 마지막에 한 자리만 더한 해석문이 포함된다.
2. k자리 암호에서 마지막 두 숫자가 26 이하면 k-2자리 암호 해석문에다가 두 자리만 더한 해석문이 포함된다.
-> dp[i] = dp[i - 1] + dp[i - 2]

⚠️ 주의 사항
k자리 암호에서 제일 마지막 숫자가 0인데 그 앞 숫자까지 본 두 자리 숫자가 0이 되거나 26보다 크면 암호 해석이 아예 불가능하다.
e.g. 1210은 암호 해석 가능 / 1230은 암호 해석 불가능 / 1200은 암호 해석 불가능

3. 초기값 정하기
dp[0] = 1
dp[1]은 첫 번째 숫자가 0이 아닐 때만 1이고, 0이면 암호 해석 불가능이므로 바로 0을 출력한다.

#include <iostream>
#include <string>

#define MAX 5001

using namespace std;

long long dp[MAX];

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

    string code;
    cin >> code;

    dp[0] = 1;
    if (code[0] == '0')
    {
        cout << '0';
        return 0;
    }
    else
    {
        dp[1] = 1;
    }

    for (int i = 2; i <= code.length(); i++)
    {
        int temp = stoi(code.substr(i - 2, 2));
        if (code[i - 1] == '0')
        {
            if (temp > 26 || temp == 0)
            {
                cout << '0';
                return 0;
            }
            dp[i] = dp[i - 2];
        }
        else if (code[i - 2] == '0' || temp > 26)
        {
            dp[i] = dp[i - 1];
        }
        else
        {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000;
        }
    }
    cout << dp[code.length()];
    return 0;
}