[백준] 알고리즘 2011번 - 암호코드 문제

#include <bits/stdc++.h>
using namespace std;
long dp[5001];
int number[5001];
int main() 
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	string s;
	int mod = 1000000;
	 
	cin >> s;
	s = '0' + s;
	dp[0] = 1;
	for (int i = 0; i < s.size(); i++) {
		number[i] = s[i] - '0';
	}
	for (int i = 1; i <= s.size(); i++) {
		if (number[i] > 0) {
			dp[i] += dp[i - 1];
			dp[i] %= mod;
		}
		if (number[i - 1] == 1 || (number[i - 1] == 2 && number[i] <= 6)) {
			dp[i]=dp[i-2]+dp[i];
			dp[i] %= mod;
		}
	}
	cout << dp[s.size()-1];
	return 0;
}

---

문제의 접근을 쉽게 생각해보자.

2 5 1 1 4 의 암호를 입력받았다고 생각해보자.

암호의 자릿수에 따라 몇 가지의 알파벳으로 변환이 되는지 dp에 저장하면된다.

즉 첫 dp[1]에는 2= B만 올 수 있다.

두번째 5는 2,5=B,E 또는 25 = Z 2가지의 경우가 올 수 있다.

경우의 수 두가지를 생각해보면

• 0보다 큰 수의 한자리씩 해보는 경우
• 두자리 수 의 1★(0~9) 2★(0~6) 경우를 가지는 경우