백준 2011번: 암호코드

[문제 링크]

2011번: 암호코드

---

암호를 해석하는 경우의 수를 구하는 방법은 다음과 같다.

 

1) 첫번째 자리 숫자가 0이면 암호를 해석할 수 없다.

 

2) 첫번째 자리 숫자가 1~9 일 때, 이 숫자를 알파벳으로 바꾼 다음 두번째 자리 숫자를 첫번째 자리로 했을 때 만들 수 있는 암호의 수

 

3) 첫번째 자리와 두번째 자리 숫자가 10~26 일 때 이 숫자를 알파벳으로 바꾼 다음 세번째 자리 숫자를 첫번째 자리로 했을 때 만들 수 있는 암호의 수

 

따라서, 암호를 해석하는 경우의 수는 2번 + 3번이 되며, 이를 탑다운 방식으로 구현하면 원하는 결과를 얻을 수 있다.

---

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

const int MOD = 1000000;
int memo[5000];
string str;

int Topdown(int start)
{
	if (start == str.length()) return 1;

	int& ret = memo[start];
	if (ret != -1) return ret;

	ret = 0;

	if (str[start] != '0')
	{
		ret += Topdown(start + 1);

		if (start + 1 < str.length() && (str[start] - '0') * 10 + (str[start + 1] - '0') <= 26)
			ret += Topdown(start + 2);
	}

	return ret %= MOD;
}

int main(void)
{
	memset(memo, -1, sizeof(memo));
	cin >> str;

	cout << Topdown(0) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 98 day