[DP #21] (BOJ 2011) 암호코드

문제

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

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

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

입력

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

출력

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

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

 

 

---

 

접근법

처음에 완전 잘못 생각하고 있었다.

어떤 수 N에서 DP를 구한게 아니라 전체 수 중 자릿수와 3이상인 수의 개수를 통해 구하려고 했다.

 

그러면 고려해야할 점이 정말 많아져서 답이 없어진다.

 

그래서 하나의 암호 안에서 해결하는 것이로 변경했다.

 

예를 들어 1232가 있다고 생각하자.

1232 다음으로 1이 올때, 1은 어떤 경우가 있을까?

i) 1따로 오는 경우
ii) 2와 함께 12로 오는 경우

 

 

DP[i] = j : i번째까지의 경우의 수 j 라고 할때

이를 DP로 나타내면

i) DP[5] = DP[5-1]
ii) DP[5] = DP[5-2]

 

따라서, DP[5] = DP[4] + DP[3]

 

근데 만약에 두 숫자가 26을 넘어가면 표현할 수 없으므로 DP[N-2] 를 더해주면 안된다.

 

그리고 만약 i번째 수가 0이면 어떻게 될까?

DP[N-1] 은 더해주면 안된다.

왜냐하면 0 독단적으로 표현할 수 없기 때문이다.

 

여기서 표현할 수 없을때 0을 출력하라고 하는데

표현할 수 없는 경우는 다음과같다.

 

i) 0으로 시작하는 경우
ii) 0이 두번이상 연속으로 나오는 경우

처음에 1000은 1과 10이므로 2인 줄 알고 코딩을 했는데 틀렸다....

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#define MAX 5002

using namespace std;

string n;

int arr[MAX];
int dp[MAX];

// string을 int 배열로 변경
int change() {
	int cnt = 0;
	for (int i = 0; i < n.size(); i++) {
		arr[i + 1] = (int)(n[i] - '0');
		if (arr[i + 1] == 0)
			cnt++;
	}
	return cnt;

}

void init() {
	dp[0] = 1;
	dp[1] = 1;

	for (int i = 2; i <= n.size(); i++) {
		int tmp = arr[i] + arr[i - 1] * 10;

		if (arr[i] != 0) {
			dp[i] += (dp[i - 1]) % 1000000;
		}

		if (tmp <= 26 && tmp >= 10) {
			dp[i] += (dp[i - 2]) % 1000000;
		}
	}
}

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

	cin >> n;
	int cnt = change();
    
	if (arr[1]==0 || n.size() == cnt) {
		cout << '0';
		exit(1);
	}


	init();


	cout << dp[n.size()] % 1000000;
}

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ