[BOJ]백준 2011번: 암호코드(C++) / DP

www.acmicpc.net/problem/2011

2011번: 암호코드

주어진 알파벳 string의 해석 경우의 수를 구하는 DP문제

수를 한 자리, 두 자리 씩 끊을 때 나올 수 없는 숫자의 범위가 있기 때문에 그 경우를 고려해주어야 한다.

-2만큼 이전에 있는 인덱스를 참조하기 때문에 base case를 위해 앞에 dummy string을 추가해주었다.

#include <iostream>
#include <string>
#define MOD 1000000
using namespace std;
string str;
int dp[5005] = { 1,1 };
int main() {
	cin >> str;
	str.insert(0, "00");
	for (int i = 2; i < str.length(); i++) {
		if (i > 2) {
			int num = (str[i - 1] - '0') * 10 + (str[i] - '0');
			if (num >= 10 && num <= 26)
				dp[i] = (dp[i] + dp[i - 2])%MOD;
		}
		int num = str[i] - '0';
		if (num >= 1 && num <= 9)
			dp[i] = (dp[i] + dp[i - 1]) % MOD;
	}
	printf("%d", dp[str.length() - 1]);
	return 0;
}