[2011] 암호코드

문제 출처 : https://www.acmicpc.net/problem/2011

분류 : 다이나믹 프로그래밍

백준 2011 암호코드

DP

---

구현 포인트

1) DP로 2자리로 끝나는 경우, 1자리로 끝나는 경우를 저장해준다.

2) 해석이 안되는 경우에는 0을 찍어야 한다.

이 문제는 다소 쉬우나 정답률이 낮다.

이유는 나처럼 멍청한 사람들이 해석이 안되는 경우에 대해 고려하지 않아서... 일 것이라는 생각이 든다.

한창 그것 때문에 틀렸습니다가 떠서 여기 글을 남겨 놓기로 하였다.

코드는 아래와 같다.

#include<iostream>
#include<string>
#define MOD 1000000
using namespace std;
 
int DP[5000][2];
int main() {
    string str;
    int len;
    cin >> str;
    len = (int)str.length();
    if (len == 1) { if (str[0] != '0') DP[0][0] = 1; }
    else {
        DP[0][0] = 1;
        for (int i = 1; i < len; i++) {
            if(str[i]!='0')
                DP[i][0] = (DP[i - 1][0] + DP[i - 1][1]) % MOD;
            if (str[i - 1] == '1' || (str[i - 1] == '2' && str[i] < '7')) {    
                DP[i][1] = DP[i - 1][0];
            }
        }
    }
    cout << (DP[len - 1][0] + DP[len - 1][1]) % MOD << '\n';
    return 0;
}