암호코드 2011

문제

접근 방법

2만 존재한다면 B일 것이다.
2, 5만 존재한다면 "BE" 또는 "Y"일 것이다.
2, 5, 1만 존재한다면 "BEA" 또는 "YA" 일 것이다.
2, 5, 1, 1만 존재한다면 "BEAA" 또는 "YAA" 또는 "BEK" 또는 "YAK"일 것이다.
2, 5, 1, 1, 4만 존재한다면 안 봐도 6개일 것이다. 왜냐하면 앞에서 나온 방식대로라면 26을 넘지 않는 경우 앞과 2번째 앞에서 문자를 더해 만들어지기 때문이다.
26을 넘는다면 앞을 유지할 것이다.

암호가 잘못되어 해석할 수 없는 경우는 무엇일까?
9999로 됐더라도 해석은 가능하다. 그렇기에 0이 들어간 경우라고 생각했다.
01의 경우 존재할 수 있는 경우가 없다.
1601이면 어떨까 존재할 수 없다.
1201이면 존재할 수 있다.

1의 경우 "A"
12의 경우 "AB", "L"
120의 경우 "AT"
1201의 경우 "ATA"이다.
0이 나온 경우 두 번째 앞에 있는 것을 가져온다.

코드

#include <iostream>
#include <string>
#include <vector>
typedef unsigned long long ull;
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string pw;
    cin >> pw;
    vector<int> dp(pw.size() + 1);
    if (pw[0] == '0')
    {
        cout << 0;
        return 0;
    }
    dp[0] = 1, dp[1] = 1;
    for (int i = 1; i < pw.size(); ++i)
    {
        if (pw[i] == '0')
        {
            if (pw[i - 1] <= '2' && pw[i - 1] > '0')
            {
                dp[i + 1] = dp[i - 1];
            }
            else
            {
                cout << 0;
                return 0;
            }
        }
        else
        {
            if (((pw[i - 1] == '2' && pw[i] <= '6') || (pw[i - 1] < '2')) && pw[i - 1] > '0')
            {
                dp[i + 1] = (dp[i] + dp[i - 1]) % 1000000;
            }
            else
            {
                dp[i + 1] = dp[i];
            }
        }
    }
    cout << dp[pw.size()];
}

풀이

0에 대한 처리가 귀찮은 문제라고 생각한다.

0이 2번 연속인 경우, 0으로 시작한 경우, 중간에 0이 있지만 0의 앞에 숫자가 2를 초과한 경우는 제외해주어야 하고

뒤의 숫자가 0이고 앞의 숫자가 2 이하인 경우 (2번째 앞의 수를 가져온다)
합쳐서 26 이하인 경우 (2번째 앞, 1번째 앞을 합쳐서 가져온다)
그 외에는 1번째 앞의 숫자를 가져온다.

이런 예외들을 생각하고 풀어야 하므로 때문에 꼬이기 쉽다고 생각한다.