[BOJ/C++] 2011 암호코드

문제

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

풀이

반례도 많고, 점화식을 생각하는 게 어려웠다😭

첫 번째 자리가 0이면 잘못된 경우이므로 0 출력

1) 현재 자리 숫자가 0보다 클 때 : dp[i-1] 값을 더한다.
ex) 2 5 1 1 4 에서 빨간색까지 이미 구했다고 하면,
2 5 1 1 / 25 1 1 / 2 5 11 / 25 11
네 가지 경우에 4를 붙일 수 있으므로 4를 더할 수 있음

2) 이전 자리 수와 현재 자리 수를 두 자리 숫자로 봤을 경우 10~26 사이의 숫자에 해당할 때 : dp[i-2] 값을 더한다.
ex) 2 5 1 1 4 에서 빨간색까지의 경우인
2 5 1 / 25 1
두 가지 경우에 14를 붙일 수 있으므로 2를 더할 수 있음

<dp 배열 채우는 코드 흐름>

dp[0] = 1;

dp[1] = 1;

dp[2] = 1;
dp[2] = 2;

dp[3] = 2;

dp[4] = 2;
dp[4] = 4;

dp[5] = 4;
dp[5] = 6;

코드

#include <iostream>
#include <string>

using namespace std;

int dp[5001];
int arr[5001];

int main() {
	string str;
	cin >> str;
	for (int i = 1; i <= str.size(); i++)
		arr[i] = str[i - 1] - '0';

	if (str.size() == 1 && str[0] == '0') {
		cout << 0;

		return 0;
	}
	else {
		dp[0] = 1;
		for (int i = 1; i <= str.size(); i++) {
			if (arr[i] >= 1 && arr[i] <= 9) {
				dp[i] = (dp[i - 1] + dp[i]) % 1000000;
			}

			if (i == 1)	continue;

			int tmp = arr[i] + arr[i - 1] * 10;
			if (tmp >= 10 && tmp <= 26) {
				dp[i] = (dp[i - 2] + dp[i]) % 1000000;
			}
		}
	}

	cout << dp[str.size()];

	return 0;
}