백준 2011번 암호코드 C++

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

간단한 dp문제처럼 보이지만 예외처리를 굉장히 많이 해줘야 한다. 푸는데 시간이 꽤 많이 걸렸다.

몇 가지 예를 들어보면 26일 때는 (26), (2, 6) 두 개가 가능하고 27은 (27) 한 개만 가능하다.

30은 불가능하지만 20은 가능하다.

110은 11까지만 봤을때는 (11), (1, 1) 두 개가 가능하지만 110까지 다 봤을 때는 110 하나만 가능하다.

이런 예외들을 처리하는게 상당히 까다로웠다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

const int DIV = 1000000;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string str;
	cin >> str;
	vector<int> v(str.length() + 2, 0);
	vector<int> dp(5001, 1);
	for (int i = 1; i <= str.length(); i++) {
		v[i] = str[i - 1] - '0';
	}
	if (v[1] == 0) {
		cout << 0;
		return 0;
	}
	dp[1] = 1;
	for (int i = 2; i <= str.length(); i++) {
		if (v[i - 1]==0) {
			if (v[i] == 0) {
				cout << 0;
				return 0;
			}
			else {
				dp[i] = dp[i - 1];
			}
		}
		else if (v[i-1] > 2) {
			if (v[i] == 0) {
				cout << 0;
				return 0;
			}
			dp[i] = dp[i - 1];
		}
		else {
			if (v[i-1] == 2 && v[i] > 6) {
				dp[i] = dp[i-1];
			}
			else {
				if (v[i] == 0) {
					dp[i] = dp[i - 1];
				}
				else {
					if (v[i + 1] == 0 && i !=str.length()) {
						dp[i] = dp[i - 1];
					}
					else {
						dp[i] = (dp[i - 1] + dp[i - 2]) % DIV;
					}	
				}
			}
		}
	}
	cout << dp[str.length()];
};