챕터3-22. DP | 문제 풀이4 - (5) 백준 No.2011 : 암호코드

암호코드 문제

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

문제요약

숫자로된 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램
A - 1, B - 2, ,,, Z - 26
ex) 25114 -> "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN"  (총 6가지)

해결 방법

1. D 정의
D[i] = "i번 문자까지 해석했을 때, 나올 수 있는 해석의 가지수"

암호는 두가지 중 하나이다.
- 1자리 수 암호 : 1(A) ~ 9(I)             -> 0 제외
- 2자리 수 암호 : 10(J) ~ 26(Z)

 

2. 점화식 세우기

case 1) 한자리 수의 암호로 보는 경우(....0)

i번째 문자까지 해석했을 때 나올 수 있는 해석의 가지수는 D[i-1]

 

case 2) 두자리 수의 암호로 보는 경우 (....00)

i번째 문자까지 해석했을 때 나올 수 있는 해석의 가지수는 D[i-2]

 

따라서, D[i] = D[i-1] + D[i-2] 
(단, 맨 앞의 첫 문자의 경우 2자리로 해석할 수 없으며 또한, 첫 문자가 0이라면 해석할 수 없고,
이후부터는 2자리로 해석할 때 앞자리가 0이면 2자리로 해석할 수 없음.
이 이유로 아래와 같이 둘을 분리해서 더해줘야함)

<Bottom-up 방식>

(1)시간복잡도
= for 문의 반복 횟수 
= O(N)

 

(2) 구현
-> 'for문을 이용한 반복문'으로 구현

#include <iostream>

using namespace std;

int d[5001];

int main()
{
    string s;
    cin >> s;

    s = " " + s; // index를 1부터 사용하기 위함.

    int s_len = s.length() - 1;

    d[0] = 1;

    for (int i = 1; i <= s_len; i++){
        
        /*s[i] 한 자리 수 인 경우로 인식하여 개수 카운트*/
        int c = s[i] - '0';
        if (1 <= c && c <= 9){
            d[i] += d[i-1];
            d[i] %= 1000000;
        }

        /*s[i-1], s[i]두 자리 수 인 경우로 인식하여 개수 카운트*/
        if (i == 1)
            continue;

        if (s[i-1] == '0') // 두 자리 중 앞자리가 0이면 두자리수가 아니므로 카운트할 필요가 없음
            continue;
        
         c = stoi(s.substr(i-1, 2));
         if(10 <= c && c <= 26){
            d[i] += d[i-2];
            d[i] %= 1000000;
         }
    }

    cout << d[s_len] << "\n";
}