[BOJ / C++] 2011번 : 암호코드

문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 5000자리 이하의 암호가 주어진다. 암호는 숫자로 이루어져 있다.

출력

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

Solved.ac 레벨

골드 V

풀이

다이나믹 프로그래밍 문제였다.

여전히 머리는 다이나믹하게 돌아가지는 않지만, 그래도 많이 풀어봤다고 이제는 규칙을 찾아 점화식을 세우는 데에 걸리는 시간이 줄어드는 기분이다.

 

dp[n]은 암호의 길이가 n일 때에 만들 수 있는 해석의 가짓수를 저장한다.

string으로 암호를 입력받은 뒤, 암호를 int형 vector에 저장하고, 암호의 길이를 len에 따로 저장을 해주었다.

 

먼저 dp[0]은 1로 초기화를 해주었다.

'해석이 아무것도 존재하지 않는 한 가지 경우'다.

 

주어진 예제 1, 암호가 25114인 경우를 통해서 점화식을 구해보자.

해당 암호를 배열로 나타내보면 아래 표와 같다.

암호의 길이	1	2	3	4	5
해당 자리의 암호	2	25	251	2511	4

dp[암호의 길이]에 들어갈 값은 해당 길이만큼의 암호를 해석하는 경우의 수를 저장하면 된다.

 

먼저 암호의 길이가 1일때.

2 = B 이므로 한 가지 경우가 존재한다.

 

암호의 길이가 2일때.

25는 각각 2 = B, 5 = E로 해석할 수도 있지만 25 자체는 알파벳 범위 내에 있으므로 25 = Y 로도 해석이 가능하다.

즉 두 가지 경우가 존재한다.

 

암호의 길이가 3일때.

251 또한 2 = B, 5 = E, 1 = A로 해석할 수 있다.

25 = Y로 해석할 수 있지만 51은 알파벳 범위를 벗어날 수 없으므로 각각 해석하는 경우만 저장한다.

따라서 2, 5, 1로 해석하는 경우와 25 , 1로 해석하는 경우를 각각 구한 뒤 저장하여 dp 배열에 저장한다.

 

.

.

.

 

이렇게 알아본 결과, 고려해야할 사항이 2가지가 있다.

 

1. 해당 자리에 새로 들어온 숫자를 알파벳 한 개에 매칭 시키는 경우

암호의 길이가 1일 때를 통해 생각해보자.

먼저 2를 2 = B로 해석하는 경우 1가지를 저장해준다.

dp 배열은 dp[0] = 1을 제외한 경우 전부 0으로 초기화되어있기 때문에 이를 이용하면 dp[1]은 dp[1] + dp[0]과 같다.

 

그 다음으로 암호의 길이가 2일때는 25를 2 = B, 5 = E로 해석하는 경우 1가지를 저장해야 한다. 암호의 길이가 1일 때 나올 수 있는 해석의 경우에 수 dp[1]에 이 1가지를 더해서 저장해야 하므로 dp[1]을 이용하면 dp[1] + dp[2] = 1 + 0 = 1이다.

 

2. 해당 자리 * 10 + 해당 자리가 알파벳 범위 (1 ~ 26)에 해당하는 경우

각 자리 숫자로 해석하는 경우의 수가 dp[2]에 담겼다. 하지만 25 두 자리 수를 한 번에 해석하는 경우의 수는 담기지 않았기에 두 자리 수가 알파벳 범위에 포함된다면 이를 알파벳으로 해석하는 경우의 수를 더해준다.

 

2자리 숫자를 먹기 때문에 현재 위치에서 2자리를 뺀 위치에 경우의 수를 더해주어야 한다.

따라서 dp[2] = dp[0] + dp[2] = 1 + 1 = 2가 된다.

 

따라서 점화식은 두 개를 세울 수가 있는데,

for(int i = 1; i <= len; i++) {
		//암호의 길이만큼 반복한다.
        if(num[i] >= 1 && num[i] <= 9) {
        	//한 자리 숫자를 해석하는 경우의 수를 저장하는 것이므로
            //직전 자리 까지의 길이의 숫자를 해석하는 경우의 수 + 현재 자리 숫자를 해석하는 경우의 수
            dp[i] = (dp[i - 1] + dp[i]) % MOD;
        }

        if(num[i-1] * 10 + num[i] >= 10 && num[i-1] * 10 + num[i] <= 26) {
        	//숫자 2개를 알파벳 1개로 해석하는 경우의 수를 더하는 것이므로
            //현재 길이 - 2 + 숫자 2개를 알파벳 1개로 해석하는 경우의 수
            dp[i] = (dp[i - 2] + dp[i]) % MOD;
        }
    }

문제에서 1000000를 나눈 나머지를 출력하라 하였으므로, dp 배열에 값을 저장할 때 해당 값으로 나눈 나머지를 저장한다.

Code

#include<bits/stdc++.h>
#define MOD 1000000

using namespace std;

string input;
int len;
vector<int> num;
long long dp[5001];

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

    cin >> input;
    len = input.length();

    num.push_back(0);
    for(int i = 0; i < len; i++) {
        num.push_back(input[i] - '0');
    }

    dp[0] = 1;

    for(int i = 1; i <= len; i++) {
        if(num[i] >= 1 && num[i] <= 9) {
            dp[i] = (dp[i - 1] + dp[i]) % MOD;
        }

        if(num[i-1] * 10 + num[i] >= 10 && num[i-1] * 10 + num[i] <= 26) {
            dp[i] = (dp[i - 2] + dp[i]) % MOD;
        }
    }

    cout << dp[len] % MOD << "\n";

    return 0;
}

 

2011번: 암호코드