백준 2011 : 암호코드 c++

코드

#include <iostream>
#include <string.h>

using namespace std;

long long dp[5001];

int main(){
	
	string password;
	int arr[5001];
	cin >> password;

	for(int i = 1; i <= password.length(); i++){
		arr[i] = password[i-1] - '0';
	}
	
	if(password.length() == 1 && password[0] == '0'){
		cout << 0 << endl;
		return 0;
	}
	
	dp[0] = 1;
	
	for(int i = 1; i <= password.length(); i++){
		if(arr[i] >=1 && arr[i] <= 9){
			dp[i] = dp[i-1]%1000000;
		}
		
		if(i == 1) continue;
		
		int temp = arr[i] + arr[i-1]*10;
		
		if(temp >=10 && temp <=26){
			dp[i] = (dp[i-2]+dp[i])%1000000;
		}
	}
	
	cout << dp[password.length()] << endl;
	
	return 0;
}

알게된 점

string으로 다뤄서 띄어쓰기 없이 입력받을 수 있다.

경우를 나누어서 dp를 더해야되는데

앞숫자랑 두자리수가 된다고 생각하는 경우 +  앞숫자랑 따로 한자리수로 생각하는 경우이다.

 

앞숫자랑 따로 한자리수로 생각하는 경우는 0만아니면 되기 때문에 그냥 dp[i] = dp[i-1] 이다.

앞숫자랑 두자리수가 된다고 생각하는 경우는 dp[i] = dp[i-2] 이다.

 

즉 만약 두자리수가 될 수 있다면, (두자리수로 봤을 때 10<=두자리수<=26이라면)

dp[i-2] 를 dp[i]에 더해주면 된다.

 

어렵당..