[BOJ/백준 2011/C++] 암호코드

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

2011번: 암호코드

 

[문제 요약]

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

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

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

 

[문제 조건]

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

- 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다.

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

- 시간 제한 : 2초

- 메모리 제한 : 128MB

 

[문제 풀이]

문제에서 요구하는 바는 일련의 숫자들을 주면 그 숫자들로 A=1, B=2 , .... , Z=26이라 했을 때 나올 수 있는 해석의 경우의 수를 구하는 것이다.

 

예를들어 입력이로 25 가 주어졌을 때 이것을 { 2=B, 5=E } 로 해석할 수도 있고, { Y=25 } 로도 해석 할 수 있다.

 

근데 주어지는 암호의 길이가 5천인데다가 모든 경우를 확인하려면 매우 오래걸릴것이다. 심지어 문제에서 엄청 큰 수로 나눴을 때 나머지를 구하라고 한다. 그래서 처음부터 DP로 접근해봤다.

 

DP[i] = i번째 숫자까지 나올 수 있는 해석의 경우로 잡고 문제를 풀어보았다.

 

그렇다면 DP[i]는 어떤 방식으로 구할 수 있을까?

 

일단 i번째 숫자를 한자리 숫자라고 생각하고 풀어보면, DP[i] = DP[i-1]과 같을 것이다. 

 

만약 두자리 숫자로 생각한다면 DP[i-2]에다가 두자리 숫자를 추가한 것과 같으니 DP[i] = DP[i-2]가 된다.

 

따라서 i-1번째 숫자와 i번째 숫자를 합했을 때 그 수가 10과 같거나 26과 같거나 작은 숫자라면 두자리 숫자로도 생각할 수 있으므로 DP[i] = DP[i-1] + DP[i-2]가 될 것이다.

 

그런데 잘 생각해보면 0으로 인해 암호를 해독할 수 없는 경우가 몇가지 있다.

• 0이 주어지는 수 맨 앞에 오는 경우
• 0앞에 수가 1도 아니고 2도 아닌경우

위 2가지 경우에는 암호 해독이 불가능하다. 왜냐하면 첫번째에 0이오면 0에 해당하는 알파벳이 없다. 그리고 중간에 0이 나오는데 0 앞에 숫자가 1,2가 아니면 알파벳의 개수를 벗어나는 수가 나오게 된다. 따라서 이 경우를 잘 처리해주면 답이 나오게 된다.

 

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>
#define pii pair<int,int>
#define mod 1000000
using namespace std;

string dt;
vector<int> dp;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> dt;

	dp.resize(dt.size());

	if (dt[0] == '0')
	{
		cout << "0";
		return 0;
	}
	else dp[0] = 1;
	for (int i = 1; i < dt.size(); i++)
	{
		if (dt[i] == '0')
		{
			if (dt[i - 1] != '1' && dt[i - 1] != '2')
			{
				cout << "0";
				return 0;
			}
			else
			{
				if (i == 1) dp[i] = 1;
				else dp[i] = dp[i - 2] % mod;
			}
		}
		else
		{
			dp[i] = dp[i - 1];
			string tmp; tmp.push_back(dt[i - 1]); tmp.push_back(dt[i]);
			int value = atoi(tmp.c_str());
		
			if (value >= 10 && value <= 26)
			{
				if (i == 1) dp[i] = (dp[i-1] + 1);
				else dp[i] = ( dp[i] % mod + dp[i - 2] % mod) % mod;
			}
		}
	}

	cout << dp[dt.size() - 1];
}

굳