[백준 2011] 암호코드 (C++)

문제 링크: https://www.acmicpc.net/problem/2011

2011번: 암호코드

1. 주의할 점

- 최대 길이가 5000자, 결과는 백만으로 나눈 나머지를 출력한다.

- 시작숫자가 0이면 불가능하므로 0을 출력한다.

 

2. 구현

- 현재 확인하는 숫자가 0이 아니라면 우선 이전값만큼 가능하다(뒤에 숫자하나만 추가하면 되기 때문)

- 현재 확인하려는 숫자와 그 전 숫자가 10~26이면 마지막 2개를 통해 새로운 글자가 표현 가능하다. 즉, DP[n-2]만큼의 암호가 또 생길 수 있다.

 

#define MOD 1000000
#include <iostream>
#include <string>
using namespace std;
long long dp[5001];
int main() {
	string str;
	cin >> str;
	dp[0] = 1;
	dp[1] = 1;
	if (str[0]-'0' == 0) cout << 0;
	else {
		for (int i = 2; i <= str.size(); i++) {
			if (str[i - 1] - '0' > 0)
				dp[i] = dp[i - 1] % MOD;
			int x = (str[i - 2] - '0') * 10 + str[i-1] - '0';
			if (10 <= x && x <= 26) 
				dp[i] = (dp[i] + dp[i - 2]) % MOD;		
		}
		cout << dp[str.size()];
	}
	system("pause");
	return 0;
}