[BOJ] 2011 : 암호코드

약간 까다로운 파싱 DP문제이다.

Top-Down 방식으로 해결했다.

예외가 없는 경우 모든 초항에 대해서 1로 설정했다.

$$DP[len-1] = 1 $$

$$ DP[N] = \begin{cases} DP[N+1], & \mbox{if arr[N+1] = 0 or arr[N+2] = 0} \\ subDP[N], & \mbox{if arr[N+1]}\ne\mbox{0 and arr[N+2] }\ne\mbox{0} \end{cases} $$

$$ subDP[N] = \begin{cases} DP[N+1] + DP[N+2], & \mbox{if arr[N] = 1} \\ DP[N+1] + DP[N+2], & \mbox{if arr[N] = 2 and 1} \le\mbox{arr[N+1]}\le\mbox{6} \\ DP[N+1], & \mbox{else} \end{cases} $$

2개 항을 더하는 연산에는 MOD연산을 추가로 해주어야 한다.

또한 \( arr[N+1] = 0 \)  \(and\)  \( arr[N+2] = 0 \) 의 경우는 암호가 만들어지지 않으므로, 0을 출력하고 종료한다.

#include <bits/stdc++.h>
using namespace std;
 
#define MOD 1000000
int dp[5011];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    string s;
    cin >> s;
    int len = s.size();
    if (s[0] == '0' || len == 0) {
        cout << 0 << '\n';
        return 0;
    }
    
    dp[len] = 1;
    dp[len - 1] = 1;
 
    bool before_zero = false;
    bool zero_sum = false;
 
    if (s[len - 1] == '0') before_zero = true;
    
    for (int i = len - 2; i >= 0; i--) {
        if (before_zero) {                      
            if (s[i] == '1' || s[i] == '2') {   
                dp[i] = dp[i + 1];
                before_zero = false;
                zero_sum = true;
            }
            else {                               
                cout << 0 << '\n';
                return 0;
            }
        }
        else {
            if (s[i] == '0') {
                before_zero = true;
                dp[i] = dp[i + 1];
            }
            else if (s[i] == '1') {
                if (zero_sum) {
                    dp[i] = dp[i + 1];
                    zero_sum = false;
                }
                else {
                    dp[i] = (dp[i + 1] + dp[i + 2]) % MOD;
                }
            }
            else if (s[i] == '2') {
                if (!zero_sum && s[i + 1] >= '0' && s[i + 1] <= '6') {
                    dp[i] = (dp[i + 1] + dp[i + 2]) % MOD;
                }
                else {
                    dp[i] = dp[i + 1];
                    zero_sum = false;
                }
            }
            else {
                dp[i] = dp[i + 1];
                zero_sum = false;
            }
        }
    }
    cout << dp[0];
 
    return 0;
}