백준 2011: 암호코드

문제 요약

A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 한다. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있다. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나온다.

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

문제 분류

• 다이나믹 프로그래밍

문제 풀이

문장 전체의 경우의 수를 구하기 위해서 부분문장의 경우의 수를 알 필요가 있는 DP문제이다. 탑다운방식으로 문제를 풀었다.

주어진 입력을 문자열로 생각하고, 가령 0번 인덱스부터 끝까지 구하는 경우의 수를 DP[0]이라고 하자. 0번째 인덱스의 문자가 '1'이면 뒤의 문자가 뭐든 간에 1을 십의 자리수로 생각하던가, 따로 생각하던가의 두 가지 경우로 나눠서 합산할 수 있다. 즉, DP[0] = DP[2] + DP[1]가 된다. 1을 십의 자리로 생각하여 두 자리를 건너뛴 곳의 경우와 1로 생각하여 한 자리만 건너뛴 곳의 경우의 수를 더한 것이다.

현재 인덱스가 '2'라면, 다음 문자가 '0'~'6'인 경우에만 해당 식이 성립한다. 27은 알파벳 범위를 넘어서기 때문에 반드시 2와 7로 구분지어서 봐야한다.

'0'이라면 0을 리턴한다. 0으로 시작하는 경우는 없기 때문이다. 어떠한 알파벳이든 1~27의 숫자를 가지므로 0으로 시작하는 알파벳은 존재하지 않는다.

그 외의 경우는 그냥 한 자리로 가정하고, 다음 위치로 나간다.

이 모든 경우를 구하고, 1000000의 나머지로 대입시켜서 리턴한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int dp[5000];
string s;

int sol(int idx) {
	if (idx >= s.length() - 1) {
		if (idx == s.length() - 1 && s[idx] == '0')
			return 0;
		return 1;
	}
	if (dp[idx] != -1) return dp[idx];

	if (s[idx] == '0') dp[idx] = 0;
	else if (s[idx] == '1') dp[idx] = sol(idx + 2) + sol(idx + 1);
	else if (s[idx] == '2') {
		if (s[idx + 1] <= '6' && s[idx + 1] >= '0')
			dp[idx] = sol(idx + 2) + sol(idx + 1);
		else dp[idx] = sol(idx + 1);
	}
	else dp[idx] = sol(idx + 1);

	dp[idx] %= 1000000;
	return dp[idx];
}

int main()
{
	memset(dp, -1, sizeof(dp));
	cin >> s;
	cout << sol(0);

	return 0;
}