BOJ 2011 암호코드

boj 2011 암호코드

- 문제 링크

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

- 문제 해설

DP를 이용하여 간단히 풀 수 있는 문제이다. D[i]가 주어진 암호의 i번째까지에서 해석할 수 있는 가짓수라고 하자. 끝 두자리의 숫자가 10 ~ 26 범위이면 한자리 숫자 2개가 될 수도 있고 두자리 숫자 1개가 될 수도 있다는 점을 생각하면 문제를 쉽게 해결할 수 있다. 생각해볼 사항들이 무엇이 있는지 살펴보자.

1. 암호의 처음 숫자가 0일 시에는 0을 출력한다.
2. 맨 끝 한 자리가 0인 경우는 맨 끝 두 자리가 10, 20인 경우를 제외하고는 암호가 성립할 수 없다. 예를 들면 맨 끝 두 자리가 00, 30, 40 ... 90 같은 경우는 대응되는 알파벳이 없기에 암호가 성립되지 못한다. D[i]가 전역 배열로 지정되어있어 0으로 초기화되어있기 때문에 이런 경우는 따로 코드로 구현해주지 않아도 된다.
3. 맨 끝 한 자리 숫자가 1~9 범위인 경우를 D[i] = D[i - 1]로 설정한다.
4. 맨 끝 두 자리 숫자가 10-26 범위이면, D[i] = D[i] + D[i - 2]라고 설정한다. 끝 한 자리가 1-9 범위이면서 끝 두 자리가 10-26 범위이면, 위에서 처리해놓은 D[i]에 의해 D[i] = D[i - 1] + D[i - 2] 형태이다.

- 코드 보기

code 배열은 암호를 담는 배열이고, 변수 num1은 끝 한 자리를 num2는 끝 두 자리를 의미한다.

#include <iostream>
using namespace std;

string code;
int D[5005];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> code;

    D[0] = 1;
    D[1] = 1;

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

    for (int i = 2; i <= code.size(); i++)
    {
        int num1 = code[i - 1] - '0';
        int num10 = (code[i - 2] - '0') * 10 + code[i - 1] - '0';

        if (num1 != 0) D[i] += (D[i - 1]) % 1000000;
        if (num10 >= 10 && num10 <= 26) D[i] += (D[i - 2]) % 1000000;
    }

    cout << D[code.size()] % 1000000;
}