[ 백준 2011] 암호코드 (C++)

백준의 암호코드(2011) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 주어진 숫자를 영어로 바꿔서 해석할 때, 총 몇가지로 해석할 수 있는지를 구하는 문제이다. 먼저 본인은 문제를 해결하기

   위해서 DP[] int형 배열을 하나 사용해주었다.

   DP[a] = b 의 의미는 "a번째 숫자까지 읽을 수 있는 단어의 갯수는 b개입니다" 이다.

   쉬운 예로 문제가 돌아가는 형식을 이해하고, 자연스럽게 점화식을 도출해보자.

   "1234" 라는 숫자가 있다.

   먼저, DP[1]의 값을 얼마일까?? 아마 1일 것이다. 왜냐하면, 1번째 숫자까지 읽을 수 있는 단어의 갯수는 1을 영어로 바꾼

   'A' 한개만 존재하기 때문이다. 1보다 이전에 존재하는 숫자도 없기 때문에 'A'한개만 읽을 수 있으므로 DP[1] = 1이다.

   그렇다면 2로 가보자.

   2같은 경우에는, 2가지 경우로 갈리게 된다.

   1. 앞에 숫자인 '1'을 A로 읽고, '2'를 B로 읽어서 "AB"라는 단어를 만드는 경우.

   2. 앞에 숫자와 합쳐서 '12' 를 "L"로 읽는 경우

   이렇게 2가지 경우가 있다.

   1번의 경우는 어떻게 계산을 해줘야 할까?? DP[1]의 값에다가 DP[2]의 값을 더해주면 된다.

   초기값으로 DP[2] = 0으로 설정되어 있을 것이다. DP[1]의 값에다가 + DP[2]를 해주면 1 + 0 = 1 로 1이 된다.

   이렇게 계산해주는 이유를 알아보자.

   저 값이 DP[2]가 아닌 DP[200] 이라고 생각을 해보자. DP[200]인 경우에, 199번째 값을 A로 따로 읽고, 200번째 값을 B로

   따로 읽는 경우라고 생각을 해보자. 이 경우에는, 199번째 숫자까지 읽을 수 있는 단어의 갯수 + DP[200]이 된다.

   물론 이 식을 충족하기 위해서는 DP[0] = 1이라는 초기조건이 필요하다.

   다시 처음으로 돌아와서 DP[1]을 다시 계산해보자. DP[1]의 경우, DP[2]를 계산한것과 같이 계산한다면

   0번째 단어까지 읽을 수 있는 단어의 갯수 + DP[1]이라는 이야기인데, 0번째 단어까지 읽을 수 있는 단어의 갯수라는 말 자체가

   모순적이다. 하지만, 이 식을 위해서 DP[0] = 1이라는 초기값을 설정해주면, DP[1] = 1 이라는 결과를 얻어낼 수 있다.

   2번의 경우는 어떻게 계산을 해줄까?? 2번의 경우도 1번과 똑같다. 1번에서는 자기 이전의 숫자를 다른 단어로 취급하였지만,

   이번에는 하나의 단어로 취급을 해줘야 한다. 위에서 말했듯이, 200번째 단어라고 생각해보면, 198번째까지 읽을 수 있는

   단어의 갯수 + DP[200]이 된다.

 

   즉, 점화식을 도출해내자면...

   DP[A] = DP[A-1] + DP[A]

   DP[A] = DP[A-2] + DP[A] 이렇게 2개의 식이 성립된다.

   물론, 조건이 붙어야 한다.

   DP[A] = DP[A-1] + DP[A] 라는 식에는, Arr[A]의 값이 1 ~ 9 사이여야만 하고,

   DP[A] = DP[A-2] + DP[A] 라는 식에는, A가 1번째 단어가 아니고, Arr[A-1] * 10 + Arr[A]를 한 값이, 10 ~ 26 (알파벳범위) 여야

   한다는 조건이 붙어야 한다.

[ 소스코드 ]

#include<iostream>
#include<string>
 
#define endl "\n"
#define MAX 5000
#define Moduler 1000000
using namespace std;
 
int Arr[MAX];
int DP[MAX] , Len;
string Inp;
 
void Input()
{
    cin >> Inp;
    Len = Inp.length();
    for (int i = 1; i <= Len; i++)
    {
        Arr[i] = Inp[i - 1] - '0';
    }
}
 
void Solution()
{
    if (Len == 1 && Inp[0] == '0')
    {
        cout << 0 << endl;
        exit(0);
    }
 
    DP[0] = 1;
    for (int i = 1; i <= Len; i++)
    {
        if (Arr[i] >= 1 && Arr[i] <= 9)
        {
            DP[i] = (DP[i - 1] + DP[i]) % Moduler;
        }
 
        if (i == 1) continue;
 
        int Temp = Arr[i] + Arr[i - 1] * 10;
        if (Temp >= 10 && Temp <= 26)
        {
            DP[i] = (DP[i - 2] + DP[i]) % Moduler;
        }
    }
    
    //for (int i = 1; i < Len; i++)
    //{
    //    cout << "DP[" << i << "] = " << DP[i] << endl;
    //}
    cout << DP[Len] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}