[C++] BOJ, 백준 2011 - 암호코드

문제 링크

2011번: 암호코드

문제 풀이

이번 문제는 DP 문제이다. DP 문제는 규칙성을 찾는것이 중요하다고 생각했기 때문에, 자릿수를 1부터 늘려가면서 규칙을 찾아보았다.

규칙 찾기

입력값이 '1'일 경우, [ 1 ] 만 가능하기 때문에 답은 1일 것이다.

입력값이 '11'일 경우, [ 1, 1 ], [ 11 ] 이므로 답은 2이다.

입력값이 '111'일 경우, [ 1, 1, 1 ], [ 1, 11 ], [ 11, 1 ] 로 답은 3이다.

입력값이 '1111'일 경우, [ 1, 1, 1, 1 ], [ 1, 1, 11 ], [ 1, 11, 1 ], [ 11, 1, 1 ], [ 11, 11 ] 로 답은 5이다.

입력값이 '11111'일 경우, [ 1, 1, 1, 1, 1 ], [ 1, 1, 1, 11 ], [ 1, 1, 11, 1 ], [ 1, 11, 1, 1 ], [ 11, 1, 1, 1 ], [ 11, 1, 11 ], [ 11, 11, 1 ] 로 답은 8이다.

여기까지 왔다면, 무언가 규칙이 보일 것이다. [ 1, 2, 3, 5, 8, .... ]

이 문제의 규칙으로 피보나치 수열이 나오게 된다. 따라서 기본적으로 피보나치 수열을 따르되, 중간중간 발생하는 예외 사항에 대해서 처리를 해주어야 한다.

예외 처리

입력값 중, 0이 포함된다면, 0의 위치에 따라 답이 달라지게 된다. 만약 '0123' 이라면, 0이 단독으로 사용될 수 없기 때문에, 답은 0이 나와야 한다.

0이 중간에 위치한다면, '10203040'일 경우, 0은 단독 사용이 불가하고, 무조건 '10' 혹은 '20'일 경우에만 사용이 가능하다. 따라서 '30', '40'이 나오는 상황도 배제되어야 한다.

두 자리의 입력값이 26 이상일 경우, '31' 과 같은 입력값은 오직 [ '3', '1' ] 로만 사용할 수 있기 때문에, 이전 항과 같은 값을 가진다고 생각했다. 따라서 n - 1, n번째 문자가 '3', '1'일 경우, dp[n] = dp[n - 1]로 설정해주었다.

정답 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define fast ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define ll long long
ll mod = 1000000;
ll dp[5001];

int main() {
    fast;
    string pw;
    cin >> pw;
    dp[0] = 1;
    dp[1] = 1;
    if (pw[0] == '0') cout << 0;
    else {
        for (int i = 1; i < pw.length(); i++) {
            if (pw[i] == '0' && (pw[i - 1] == '1' || pw[i - 1] == '2')) dp[i + 1] = dp[i - 1] % mod;
            else if (pw[i] == '0' && (pw[i - 1] == '0' || pw[i - 1] >= '3')) {
                dp[pw.length()] = 0;
                break;
            }
            else if ((pw[i] <= '6' && pw[i - 1] == '2') || (pw[i - 1] == '1')) dp[i + 1] = (dp[i] + dp[i - 1]) % mod;
            else dp[i + 1] = dp[i] % mod;
        }
        cout << dp[pw.length()];
    }
}