[1일 1알고] G5 2011 암호코드

https://www.acmicpc.net/problem/2011

 

 

"정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다."

라는 문장이 있는 것으로 보아 모든 경우를 직접 계산하는 것은 아니고, dp를 통해 계산하게 될 것임을 알 수 있습니다.

 

11이라면 AA 혹은 K로 해석될 수 있습니다.

따라서 현재 시점에서 숫자를 따로 해석하는 경우와 합쳐서 해석하는 경우를 나눠서 보아야 합니다.

 

그렇다면 index i일  따로 해석하는 경우에는 i-1 시점의 경우의 수, 같이 해석하는 경우는 i-2 시점의 경우의 수와 같기 때문에

전체 경우의 수 dp[i] = dp[i-1] + dp[i-2]가될 것입니다.

 

하지만 이것은 숫자가 따로 + 합쳐서 해석이 가능한 경우에만 그렇고 모든 경우를 따져봐야합니다.

---

1. 숫자가 1~9인 경우  (따로 해석만 가능한 경우)

숫자가 1~9인 경우는 i-1(i>=2)의 숫자가 0인 경우입니다. 앞의 숫자가 0이기 때문에 해당 숫자는 0앞의 숫자와 묶여서 해석되었을 것이고 따라서 해당 시점에서는 dp[i] = dp[i-1]입니다.

---

2. 숫자가 합쳐서 해석 가능한 두자리 수 인 경우 (다만 숫자 != 10 || 숫자 != 20)

숫자가 따로 + 합쳐서 해석 가능한 경우는 숫자가 두자리 수이며 알파벳 범위 안에 있는 10 ~ 26인 경우입니다.

다만 10이나 20인 경우는 한 자리 수가 0이기 때문에 별도의 경우로 보아야 합니다.

 

이 경우에는 위에서 언급한 dp[i] = dp[i-1] + dp[i-2]입니다.

---

3. 숫자가 10혹은 20으로 해석되어야 하는 경우 (합쳐서만 해석이 가능한 경우)

30, 40 ....는 알파벳 범위 밖에 있기 때문에 이 경우에는 해석이 불가합니다.

10, 20인 경우에는 이렇게 해석하지 않으면 해석이 실패하기 때문에 i-1번째 해석을 무시하고 i-2시점의 경우의 수만 받아옵니다.

따라서 dp[i] = dp[i-2]입니다.

---

코드

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int size = s.size();
    vector<long long> v(size, 0);

    v[0] = 1;

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

    if (s[1] == '0')
    {
        if (s[0] == '1' || s[0] == '2')
        {
            v[1] = 1;
        }
        else
        {
            cout << 0;
            return 0;
        }
    }
    else if ((s[1 - 1] - '0') * 10 + (s[1] - '0') <= 26)
    {
        v[1] = 2;
    }
    else
    {
        v[1] = 1;
    }


    for (int i = 2; i < size; ++i)
    {
        int temp = (s[i - 1] - '0') * 10 + (s[i] - '0');
        if (s[i] == '0')
        {
            if (s[i - 1] == '1' || s[i - 1] == '2')
            {
                v[i] = v[i - 2] % 1000000;;
            }
            else
            {
                v[size - 1] = 0;
                break;
            }
        }
        else if (temp <= 26 && temp >= 10)
        {
            v[i] = (v[i-1] + v[i-2]) % 1000000;
        }
        else
        {
            v[i] = v[i - 1] % 1000000;
        }
    }

    cout << v[size - 1];

    return 0;
}

첫 시점에서는 앞에 숫자가 존재하지 않기 때문에 별도로 처리가 필요합니다.

 

0처리를 신경쓰지 않는다면 실수하기 쉬운 느낌입니다.