[C++] 백준 2011번 암호코드

다이나믹 프로그래밍 문제입니다.

n의 숫자가 주어졌을 때 가능한 경우가 몇개인지 찾는 문제입니다.

A = 1
B = 2
C = 3
....
Y = 24
X = 25
Z = 26
으로 하였을 때

25의 경우
1. BE
2. X
처럼 두가지 경우가 가능합니다.

한자리수가 1~9일 때

DP[c] = DP[c - 1];

두자리수가 10~26일 때

DP[c] = DP[c - 2] + DP[c];

계산이 불가능 할 때

if (stoi(n.substr(0, 1)) == 0) {
	cout << "0" << endl;
	return 0;
}

 

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

int DP[5010];
int mod = 1000000;

int main(int argc, char *argv[])
{
	int c = 2;
	int sum;
	string n;

	memset(DP, 0, sizeof(DP));
	DP[0] = 1;
	DP[1] = 1;

	cin >> n;
	
	if (stoi(n.substr(0, 1)) == 0) {
		cout << "0" << endl;
		return 0;
	}

	while (c <= n.length()) {		
		int x = stoi(n.substr(c - 1, 1));
		int y = stoi(n.substr(c - 2, 2));

		if (x > 0 && x < 10) {
			DP[c] = DP[c - 1];
		}
		if (y > 9 && y < 27) {
			DP[c] = (DP[c - 2] + DP[c]) % mod;
		}

		c++;
	}
	sum = DP[n.length()];
	cout << sum << endl;

	return 0;
}