백준, BOJ, 2011번, 암호코드 : C++ [CPP]

물론 이것도 DP 문제다.

왜냐하면.. 경우의 수가 무지막지하게 늘어나기 때문이다.

 

 

이런 실버 1문제를 1시간이나 걸리다니...

예외를 찾는게 너무 오래걸렸다.

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

 

---

 

#맞은 풀이

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int DIV = 1000000;

string s;
long long dp[5001];
int num[5001];


int main() {
    cin >> s;
    int length = s.size();
    long long ans;

    //1부터 시작하게 바꿈.
    for (int i = 0; i < length; i++) {
        num[i + 1] = s[i] - '0'; //문자열이므로 int로 바꿀 때
    }
    dp[0] = 1;
    dp[1] = 1;


    //0으로 시작하면 암호가 아님
    if (num[1] == 0) {
        cout << '0';
        return 0;
    }

    for (int i = 2; i <= length; i++) {
        
        //#1.현재 숫자가 0일 때는 단독으로 존재 불가. 무조건 앞에 숫자랑 함께 붙어야함.
        if(num[i] == 0){
            
            //즉, 앞에 숫자와 합쳐져서 10 또는 20만 나와야함.
            if(num[i-1] == 1 || num[i-1] == 2){
                dp[i] = dp[i-2];
                 dp[i] %= DIV;
                continue;
            }else{
                //합쳐야 하지만 30 이상이 되면 해석 불가
                cout << '0';
                return 0;
            }
        }
        //#2. 현재 숫자가 0이 아니라면
        //#2-1 앞에 숫자와 합쳐질 수 있다면(1~26)
        if (num[i - 1] * 10 + num[i] <= 26 && num[i - 1] != 0) {
            dp[i] = dp[i - 2] + dp[i - 1]; //맨 뒷자리 2개를 합쳐도 되고, 따로 해도 되고
            dp[i] %= DIV;
            continue;
        }
        //#2-2 앞에 숫자와 합쳐질 수 없다면
        dp[i] = dp[i - 1];
        dp[i] %= DIV;

    }

    ans = dp[length];


    ans %= DIV;

    cout << ans;
    return 0;
}

 

 

즉, N번째 수를 붙여서 해석할 때

N-1번째 까지의 수 중에서 현재 수와 합칠 수 있을까? 없을까?

를 계산하고 예외를 적용하면 된다.

합친다면 

N-2번째 경우 모두에서 그냥 뒤에다 합친 숫자를 추가하는 것이다.

합치지 않는다면

N-1번 경우 모두에서 그냥 뒤에다 하나만 추가하는 것이다.

 

즉, 3210 이라고 한다면

 

첫 번째 K=1

3

 

두 번째 K=2

3,2

 

세 번째 K=3

3,21   -> 첫번째에서 가져온(K-2) 수 조합에 합친 숫자를 추가

3,2,1 ->  두번째에서 가져온(K-1) 수 조합에 그냥 뒤에다 숫자 추가

 

네 번째 K=4

3,21,0 (x)

3,2,10 (o) ->0이므로 무조건 앞 숫자와 함께 와야함-> 두번째에서 가져온(K-2) 숫자에 합친 숫자 추가

 

예외 조건으로 0으로 절대로 시작하면 안된다.