[BAEKJOON] 2011 암호코드 (C++)

https://www.acmicpc.net/problem/2011

2011번: 암호코드

 

문제

문제는 숫자로 암호화된 문자열을 다시 문자형식으로 바꿀 때 가능한 경우의 수를 구하는 문제이다.

일반적인 DP냄새가 나는 문제

 

얼마전 스터디에서 https://www.acmicpc.net/problem/2302 문제를 풀었는데, DP점화식을 구성하는 것이 비슷하다.

 

풀이

숫자로 암호화된 문자열을 문자로 바꾸는 경우는 두가지이다.

1. 숫자 하나만 보고 문자로 변환

2. 숫자 두개를 묶어서 문자로 변환

 

즉 두개를 묶을 수 있다면, 두개를 묶는 조합의 수가 총 몇개나 가능한지를 확인하는 문제라는 점에서 2302번과 유사하다.

 

이러한 경우 기본적인 점화식 구성은 다음과 같다.

dp[i] = dp[i - 1] + dp[i - 2];

dp[i]가 의미하는 바는 i번째까지 가능한 경우의 수이다.

1. 바로 전에 있는 i-1번째 문자와 묶어서 해석하는 경우의 수 = dp[i-2] (i번째와 i-1번째를 제외하고 생각한다고 가정하면 직관적이다)

2. i번째 수를 있는 그대로 해석하는 경우의 수 =  dp[i-1]

 

하지만 이 문제에서 암호화될 수 없는 케이스가 존재한다. 

1.  한자리수로 해석할 때 숫자가 0이라면 불가능하다.

2. 두자리수로 해석할 때 숫자가 10~26사이가 아닌 경우는 불가능하다.

 

이 두 케이스를 조건화해서 점화식을 전개하면 답을 구할 수 있다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define endl "\n"

using namespace std;

int dp[5001];
string s;

void Solve() {
	bool check1, check2;
	int num;
	cin >> s;
	if (s[0] != '0') dp[0] = 1;
	else {
		cout << 0; return;
	}
	if (s.size()>1&&s[1] != '0') dp[1] = 1;
	if ((s[0] - '0') * 10 + s[1] - '0' >= 10 && (s[0] - '0') * 10 + s[1] - '0' <= 26) dp[1]+=1;
	for (int i = 2; i < s.size(); i++) {
		check1 = check2 = false;
		
		if (s[i] != '0') check1 = true;

		num = (s[i - 1] - '0') * 10 + s[i] - '0';
		if (num >= 10 && num <= 26) check2 = true;

		if (check1 && check2) dp[i] = dp[i - 1] + dp[i - 2];
		else if (check1) dp[i] = dp[i - 1];
		else if (check2) dp[i] = dp[i - 2];
		else break;
		
		dp[i] %= 1000000;
	}

	cout << dp[s.size() - 1]% 1000000;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "r", stdin);
	Solve();


	return 0;
}