[백준] 2011번: 암호코드

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

2011번: 암호코드

예외 처리가 까다로웠는데, 보다 쉽게 푸는 방법이 있어서 그것도 같이 알아보았다.

 

최대 2자리의 수까지만 결합이 가능하기 때문에 i번째 자리까지의 최대 경우의 수를 다이나믹 프로그래밍으로 구할 때, 마지막 수가 두자리로 구했는지, 1개로 구했는지 구분해서 기록하였다.

 

처음에는 앞자리와 현재 숫자의 결합이 26을 기준으로 구분만 하였는데, 0 처리를 따로 해줘야 하더라..

 

i) 만약 해당 숫자가 0이라면

덧붙이기만 불가능하고, 결합만 가능하다.

대신 26보다 작아야 한다. 만약 그렇지 않으면 암호를 해석할 수 없는 경우이다.

 

ii) 앞자리 + 현재숫자가 26 이하라면

🌱 nonpairs[i] = pairs[i - 1] + nonpairs[i - 1]

앞 경우들에 i번째 숫자에 해당하는 암호만 덧붙이므로 pairs, nonpairs를 구분할 필요가 없다.

 

🌱 pairs[i] = nonpairs[i - 1]

pairs가 이미 된 경우는 배제한다.

 

iii) 앞자리 + 현재숫자가 26 초과이라면

🌱 nonpairs[i] = pairs[i - 1] + nonpairs[i - 1]

앞 경우들에 i번째 숫자에 해당하는 암호만 덧붙이므로 pairs, nonpairs를 구분할 필요가 없다.

 

🌱 pairs[i] = 0

해당 결합으로는 암호화가 불가능하다. 덧붙이기만 가능하다.

 

이렇게 풀려면 배열을 2개로 써야 한다.

그런데 다른 풀이를 보니 배열을 1개로만 쓰더이다...

잘 알아보니 두개의 수(i - 1, i)를 결합할 때, i - 1 단계에 이미 결합된 케이스가 다시 결합되는 중복을 막으려고 배열 2개로 나눴는데 잘 생각해보니 배열의 i - 2 값을 활용하면 되지 않는가!!!!!!!!

 

이를 위해 초기값을 0인덱스에 설정하고 숫자 배열을 1 ~ 길이 인덱스까지 반영한다.

#include <iostream>
#include <cstring>
#define MOD 1000000
using namespace std;
int dp[5000] = {0}, arr[5000] = {0};
int len = 0;
int main() {
    string str;
    cin >> str;
    len = str.length();
    for(int i = 1;i <= len;i++) {
        arr[i] = str[i - 1] - '0';
    }
    
    if(str[0] == '0') {
        cout << 0 << '\n';
        return 0;
    }
    // 초기값
    dp[0] = 1;
    for(int i = 1;i <= len;i++) {
        if(arr[i] >= 1 && arr[i] <= 9) {
            dp[i] = (dp[i - 1]  + dp[i]) % MOD;
        }
        
        if(i == 1) continue;
        
        int temp = arr[i - 1] * 10 + arr[i];
        if(temp >= 10 && temp <= 26) {
            dp[i] = (dp[i - 2] + dp[i]) % MOD;
        }
    }
    
    cout << dp[len] << '\n';
    
}