[BAE/<JOON> 문제풀이] 2011. 암호코드 (DP.043)

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

2011번: 암호코드

맞는 코드 짜놓고 컨트롤 c가 안먹어서 이전 코드로 제출하고 틀린거보고 왜틀렸는지 1시간 고민했다.

 

이 문제 함정이 많다.

 

1. 0으로 시작하는 문자열이 입력되는 경우

 

2. 10, 20처리 (30이상 제거)

 

3. 0이 2번 이상 반복되는 경우 처리

 

처음 풀 때 저 3가지 경우중 2가지 이상을 먼저 떠올리고 코드를 짰다면 당신은 천재다.

 

특히 2번이 처리하기 까다로웠다. 

 

여러 방법이 있겠지만 고민 끝에 그냥 0이 입력될 경우 offset값을 하나 줄이고 이전에 입력된 값을 검사하여,

 

3 이상이면 종료하고 아니라면 10을 곱하는 방식으로 처리를 했다.

 

이 방식이 편리한게 3번 케이스도 같이 처리되어서 굳이 따로 코드를 짤 필요가 없다.

 

어차피 0이 입력된 이상 앞에 수는 무조건 10이거나 20일 수 밖에 없기 때문이다.

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    string s;
    cin >> s;
    if (s[0] - 48 == 0) {
        cout << 0;
        return 0;
    }
    int ls = s.length();
    vector<int> arr, dp;
    arr.resize(ls + 1);
    dp.resize(ls + 1);
    arr[1] = s[0] - 48;
    int offset = 1;
    for (int i = 2; i <= ls; i++) {
        if (s[i - 1] - 48 == 0) {
            if (arr[i - offset] > 2) {
                cout << 0;
                return 0;
            }
            arr[i - offset] *= 10;
            offset += 1;
            continue;
        }
        arr[i - offset + 1] = s[i - 1] - 48;                
    }
    ls -= offset;
    ls += 1;    
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= ls; i++) {
        if (arr[i] >= 10) {
            dp[i] = dp[i - 1];
            continue;
        }
        int prev = arr[i] + arr[i - 1] * 10;        
        if (prev > 26) {
            dp[i] = dp[i - 1];
        }        
        else {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        dp[i] %= 1000000;
    }   

    cout << dp[ls];

    return 0;
}