2011번

2011번 - 암호코드

문제를 처음 보자마자 살짝 당황.

문제의 조건에서 숫자가 5000자리까지 될 수 있기 때문에 정수형 변수로는 나타낼 수 없었다.

나는 string 같은 경우 함수를 잘 모르기 때문에 구글링을 하면서 풀었다.

이 문제에서 내가 걸린 함정은 10000 같이 중간에 0 이 있는 경우에는 알파벳에서 0을 나타낼 수 있는 문자가 없기 때문에

해석할 수 없는 코드로 답이 0이 출력되어야 한다는 점이었다.

( 문제 질문 게시판에 가보면 이 점을 간과한 사람들이 올린 질문이 수두룩하다.)

이 부분을 간과해서 한참을 헤멨었다.

그리하여 처음에 완전탐색으로 풀었지만 역시나 캐시를 이용하지 않으면 시간 초과가 났다.

두번째로는 5000이라는 값을 이용하여 캐시를 사용하였다.

D[N] = N개 문자를 해석하는 방법의 수

따라서 D[N] = D[N-1] + D[N-2] 가 된다. 알파벳이 숫자로 (1~26까지 1자리 혹은 2라이 이기 때문이다.)

그리고 D[N-1] 일때는 0일 경우를 제외해줘야 하고

D[N-2] 일때는 첫째자리가 1인 경우와 2인 경우를 나눠서 가능한 경우의 수를 파악해야 했다.

그렇게 문제를 풀면 문제가 풀리게 된다.

이번 문제의 경우 DP 는 뒤에서 앞으로 푸는 코드, 앞에서 뒤로 푸는 코드로 총 2개

완전탐색 두번째 코드의 경우 앞에서 부터 확인하는 방식으로 풀었다.

(그래서 string at() 함수에 들어가는 값이 다르다)

<정답 코드 - DP>

뒤에서 앞

#include<iostream>
#include<string>
#define div 1000000;
using namespace std;
 
string code;
int len;
int ans;
int D[5001];
 
int go(int n)
{
    if (n < 0)
    {
        return 0;
    }
    if (n == 0)
    {
        return 1;
    }
    if (D[n] != 0)
    {
        return D[n];
    }
    if (code.at(n - 1) != '0')
    {
        D[n] += go(n - 1);
        D[n] %= div;
    }
    if (n >= 2)
    {
        if (code.at(n - 2) == '1')
        {
            D[n] += go(n - 2);
            D[n] %= div;
        }
 
        else if (code.at(n - 2) == '2')
        {
            if (code.at(n - 1) <= '6' && code.at(n - 1) >= '0')
            {
                D[n] += go(n - 2);
                D[n] %= div;
            }
        }
    }
    
    return D[n]%div;
}
 
int main()
{
    getline(cin, code);
    len = code.size();
 
    for (int i = 0; i < 5001; i++)
    {
        D[i] = 0;
    }
    
    
    cout << go(len) << endl;
    return 0;
}

앞에서 뒤

#include<iostream>
#include<string>
#define div 1000000;
using namespace std;
 
string code;
int len;
int ans;
int D[5001];
 
int go(int n)
{
    if (n > len)
    {
        return 0;
    }
    if (n == len)
    {
        return 1;
    }
    if (D[n] != 0)
    {
        return D[n];
    }
    if (code.at(n) != '0')
    {
        D[n] += go(n + 1);
        D[n] %= div;
    }
 
    if (n <= len - 2)
    {
        if (code.at(n) == '1')
        {
            D[n] += go(n + 2);
            D[n] %= div;
        }
 
        else if (code.at(n) == '2')
        {
            if (code.at(n + 1) <= '6' && code.at(n + 1) >= '0')
            {
                D[n] += go(n + 2);
                D[n] %= div;
            }
        }
    }
 
    return D[n] % div;
}
 
int main()
{
    getline(cin, code);
    len = code.size();
 
    for (int i = 0; i < 5001; i++)
    {
        D[i] = 0;
    }
 
 
    cout << go(0) << endl;
 
 
    return 0;
}

<완전 탐색 - 시간 초과>

앞에서 뒤

#include<iostream>
#include<string>
#define div 1000000;
using namespace std;
 
string code;
int len;
int ans;
int D[5001];
 
void go(int n)
{
    if (n > len)
    {
        return;
    }
    if (n == len)
    {
        ans += 1;
        ans %= div;
        return;
    }
 
    if (code.at(n) != '0')
    {
        go(n + 1);
    }
    if (code.at(n) == '1')
    {
        go(n + 2);
    }
 
    if (code.at(n) == '2')
    {
        if (code.at(n + 1) <= '6' && code.at(n + 1) >= '0')
        {
            go(n + 2);
        }
    }
 
 
    return;
}
 
int main()
{
    getline(cin, code);
    len = code.size();
 
    go(0);
 
    cout << ans << endl;
 
    return 0;
}