[c++] 백준 #2011 암호코드 (190822)

< 풀이 >

초급 DP문제인데 재채점 되면서 틀린 걸 다시 풀어봤다. 다행히 다른 사람들 반례 + 내 코드 만으로 풀 수 있었다. 처리 해줘야 하는 경우의 수가 복잡해질 수 있지만 핵심은 다음과 같다.

1) 0으로 시작하면 무조건 0.

2) 0이 연속으로 두 번 이상 나오면 무조건 0 출력하기

3) i번째 인덱스가 0이 아니면 DP[i]에 DP[i-1]을 더해줌

4) I-1, I번째 인덱스가 합해서 10~26 사이의 값이면 DP[i-2]를 DP[i]에 더해줌

 

10달 전에 짠 코드를 봤는데 확실히 가독성도 훨씬 좋아지고 코드 자체도 많이 좋아졌다. 역시 연습이 답인 듯. 뭔가 감회가 새로웠다.

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define MOD 1000000
ll DP[5010];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string A;
    cin >> A;

    // DP[i] = DP[i-1] + DP[i-2](26사이 알파벳이 될때)
    if (A[0] == '0') {
        cout << 0 << '\n';
        return 0;
    }
    if (A[0] != '0') DP[0] = 1LL;
    if (A[1] != '0') DP[1] = 1LL;
    
    int temp = (A[0] - '0')*10 +(A[1]-'0');
    if (temp <= 26 && temp >= 10) DP[1] += 1;
    for(int i=2; i<A.size();i++){
        if (A[i] == '0' && A[i-1] == '0'){
            cout << 0 << '\n';
            return 0;
        }
        if (A[i] != '0') DP[i] = DP[i-1] % MOD;
        int temp = (A[i-1] - '0')*10 +(A[i]-'0');
        if (temp <= 26 && temp >= 10) DP[i] = (DP[i] + DP[i-2]) % MOD;
    }
    cout << DP[A.size()-1] % MOD << '\n';
    return 0;
}