[Baekjoon,2011] 암호코드

한 글자씩 복호화를 진행는데 현재 숫자를 가르키는 위치의 숫자가 10~26인 추가적인 경우를 고려하며 탐색해야 한다. 즉 현재 숫자에 대해 아래의 두 가지 경우로 탐색하면 되는데 이는 동적 계획법을 쉽게 적용할 수 있다.

1. 한 개의 숫자를 복호화
2. 숫자가 10~26인 경우 두 자리를 복호화

하지만 예외를 처리해야 한다. 0이 처음에 나오는 경우, 0이 연속으로 두 번 나오는 경우, 30,40과 같은 숫자 배열이 나오는 경우이다. 이러한 경우는 a를 1부터 암호화 하였기 때문에 복호화를 진행할 수 없다. 이는 기저 사례를 현재 가리키는 숫자가 0인 경우 0을 반환하는 것으로 설정하여 간단히 해결 가능하다.

구현

구현된 코드를 아래에서 볼 수 있다.

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
using namespace std;

const int MOD = 1000000;

string digits;
long cache[5001];

long solve(int here)
{
	if (here == digits.size())
		return 1;
	// 현재 자리의 숫자가 0이면 만들 수 없다.
	if (digits[here] == '0')
		return 0;

	long& ret = cache[here];
	if (ret != -1)
		return ret;

	ret = 0;
	// 10~26 의 경우
	if (here + 1 < digits.size() && (digits[here] == '1' ||
		(digits[here] == '2' && digits[here + 1] <= '6')))
		ret += solve(here + 2) % MOD;
	
	return ret = (ret + solve(here + 1)) % MOD;
}

int main()
{
	cin >> digits;
	memset(cache, -1, sizeof(cache));
	
	cout << solve(0) << endl;

	return 0;
}