백준 / BOJ / 2011 암호코드 C++

www.acmicpc.net/problem/2011

2011번: 암호코드

5000자리 이하의 암호문이 주여졌을 때, 가능한 경우가 얼마인지 구하는 문제이다. (modulo 1000,000) 

문제에서 A:1 ~Z:26으로 대응되게하였으므로 앞자리가 0이면 암호가 성립되지 않는다. 또한, 70 과 같은 경우는 앞자리가 0이 아니지만, 7 다음으로 0인 케이스가 존재하기 때문에 이러한 경우도 안 된다.

 

되는 경우는 다음과 같다.

해당 자리수에 가능한 수를 dp배열을 이용해 표기하면 점화식은 다음과 같다. (dp[n] : n번째 자리에서 가능한 경우)

 

dp[n] += dp[n-1] if string[n] != '0'

dp[n] += dp[n-2] if "10" <= string[n-1 : ] <="26" 

 

암호문이 되지 않는 예외만 잘 처리한다면 어렵지 않게 풀 수 있는 문제였다.

dp[0]=1로 잡은 것은 앞에서 예외를 미리 처리했으므로 된다는 가정이 있기 때문에 1로 잡고 시작하였다. 

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

int mod = 1000000;

string crypto = "";
int dp[5001];

int main()
{
	cin >> crypto;
	memset(dp, 0, sizeof(dp));

	if (crypto[0] == '0')
	{
		cout << 0;
		return 0;
	}

	if (crypto.size() == 1)
	{
		cout << 1;
		return 0;
	}

	dp[0] = 1;
	dp[1] = 1;

	for (int i = 2; i <= crypto.size(); i++) {
		if (crypto[i - 1] != '0') {
			dp[i] += dp[i - 1] % mod;
			dp[i] = dp[i] % mod;
		}
		string s = crypto.substr(i - 2, 2);
		int val = stoi(s);
		if (val >= 10 && val <= 26) {
			dp[i] += dp[i - 2] % mod;
			dp[i] = dp[i] % mod;
		}
	}

	cout << dp[crypto.size()];
}