[백준 2011][DP][C++] 암호코드

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

2011번: 암호코드

 

DP로 접근하기까지는 쉬웠지만, 예외처리가 까다로웠던 문제였다.

 

251104로 고려해보자.

(1) 2를 볼 때, 경우의 수는 (2) 가 있다.

(2) 5를 볼 때, 경우의 수는 (2,5), (25) 가 있다.

(3) 1을 볼 때, 경우의 수는 (2,5,1), (25,1) 가 있다.

(4) 1을 볼 때, 경우의 수는 (2,5,1,1), (25,1,1), (2,5,11), (25,11) 가 있다.

(5) 0을 볼 때, 경우의 수는 (2,5,1,10), (25,1,10) 가 있다.

(6) 4를 볼 때, 경우의 수는 (2,5,1,10,4), (25,1,10,4) 가 있다.

 

정리해보자.

1. 먼저, (2)에서 (3)으로 갈 때는 (2)의 경우의 수에 1을 붙이는 방법밖에 없었다. 알파벳의 범위는 1~26이기에 (2)와 (3)을 합친 51은 알파벳이 아니기 때문이다.

 

2. (3)에서 (4)로 갈 때는 (3)의 경우의 수에 1을 붙이는 방법과 (2)의 경우의 수에 (4)와 (3)를 붙이는 방법이 있다.

 

3. (4)에서 (5)로 갈 때는 (3)의 경우의 수에 (5)와 (4)를 붙이는 방법밖에 없다. 0은 알파벳이 아니기 때문이다.

 

요약하면,

1. 만약 보고 있는 수가 0이 아니고 앞에서 본 수와 붙였을 때 10보다 작으면 dp[i] = dp[i-1]

2. 만약 보고 있는 수가 0이 아니고 앞에서 본 수와 붙였을 때 10 이상이면 dp[i] = dp[i-1] + dp[i-2]

3. 만약 보고 있는 수가 0이면 (이땐 잘못된 입력이 아니라면 (i-1)와 (i)를 붙인 값은 10 이상이다) dp[i] = dp[i-2]

 

1과 2에서 0이 아니라는 것에서 중복되고, 2와 3에서 10 이상이라는 것이 중복되므로,

 

0이 아닐 때, dp[i] = dp[i-1]

(i)와 (i-1)를 붙인 값이 10 이상이면 dp[i] = dp[i] + dp[i-2]

 

나머지 예외처리로, 잘못된 입력일 경우 0을 출력해주면 된다.

 

 

#include<iostream>
#include<string>
#define mod 1000000
using namespace std;

int main(){
    string s; cin>>s;
    int size = s.size();
    if(s[0]=='0'){
        cout<<0; return 0;
    }
    int dp[5001] = {1,1}; // dp의 0,1번째 값은 1
    for(int i=2; i<=size; i++){
        if(s[i-1]>'0') dp[i]=dp[i-1]%mod; //s의 현재값(i-1)이 0이 아닐 때
        
        int n =(s[i-2]-'0')*10 + s[i-1]-'0'; //s[i-2 ~ i-1]이 10~26일 때
        if(10<=n && 26>=n){
            dp[i] = (dp[i]+dp[i-2])%mod;
        }
    }
    cout<<dp[size];
}