[BOJ] C++ 2011: 암호코드 - DP, 예외 처리를 잘 해주자!

2011번: 암호코드

---

문제를 읽었을 때 바로 느껴지는 점은 어째서 암호코드 가짓수를 구하는 거야...? 였다. 농담이고 전에 푼 다른 DP 문제가 떠올랐다.

[BOJ] C++ 2193: 이친수 - DP 테이블링 연습하기

이 문제랑 굉장히 비슷한 과정으로 테이블을 정의하고 점화식을 찾았다. 점화식을 찾으면서 0에 대한 예외가 많이 나오겠다 싶어서 테스트케이스를 만들어서 손으로 써봤다.

 

일단 테이블링은 dp[k] = k자릿수까지 암호코드 가짓 수로 두고 252024에 대해 규칙을 찾아봤다.

k-1까지 암호를 만든 경우에 k 자리의 수 하나만 뒤에 띡 붙이는 경우는 k 자리의 수가 0만 아니면 바로 붙일 수 있다.

k-2까지 암호를 만든 경우에 k-1, k 자리의 수를 붙이는 경우는 이 수가 10 <= x <= 26을 만족해야 한다. 04 같은 수는 잘못된 암호이다. 

또, 0으로 시작하는 암호는 처음부터 잘못된 암호이므로 그냥 0을 출력해야 한다. 이렇게 점화식을 잘 찾았으면 구현은 그냥 해주면 된다.

 

나는 숫자의 자릿수에 집중해야해서 문자열로 숫자를 저장해서 구현했는데, 문자열에 저장해 놓고 정수형 배열로 옮겨서 저장하는 방법이 더 좋아 보인다. 배열로 저장하면 index에 바로 접근할 수 있고 0번 index를 비울 수 있어서 0 starting index를 신경 쓰지 않아도 된다.

/** DP 2011 암호코드 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
const int MOD = 1000000;
string s;
int dp[5050];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    int n = s.size();

    // n자리수
    // dp[i] = i자리까지 체크한 암호코드 수 0 index 주의
    if (s[0] - '0' <= 0)
        cout << "0\n";
    else
    {
        dp[0] = 1;
        for (int i = 1; i < n; i++)
        {
            if (s[i] - '0' > 0)
                dp[i] = (dp[i] + dp[i - 1]) % MOD;
            int x = stoi(s.substr(i - 1, 2));
            if (x >= 10 && x <= 26)
            {
                if (i - 2 < 0)
                    dp[i] = (dp[i] + 1) % MOD;
                else
                    dp[i] = (dp[i] + dp[i - 2]) % MOD;
            }
        }
        cout << dp[n - 1] << '\n';
    }
}