백준 2011 암호코드 (C++)

2011번: 암호코드

dp를 이용한 문제이다. 점화식을 잘 세우면 빠르게 풀 수 있다. 문제에 주어진 예시가 힌트였다. 1111111111을 차례대로 생각해보자.

• 1 : 1개
• 11 : 2개
• 111 : 3개
• 1111 : 5개
• 11111 : 8개
• 즉 dp[n] = dp[n-2] + dp[n-1]

이와 같은 점화식을 얻을 수 있다. 그러나 알파벳의 범위는 1부터 26까지, 그리고 중간에 0이 들어갈 수 도 있기 때문에 여기서 약간 변화를 주어야한다. 현재 위치의 숫자가 0인 경우, 이전의 경우의 수를 그대로 이전한다. 그 후 현재 위치, 이전 위치 숫자가 알파벳 범위 안이라면 dp\[n-2]를 합해준다. 조건에 1000000을 나눈 나머지를 출력한다고 하므로 합칠 때마다 나머지를 구해 저장해준다. 이를 반복문으로 돌려준 후 결과를 출력해준다.
나머지를 구하고 출력하는 과정에서 시간이 오래 걸렸다. 처음에는 마지막 결과만 나눠주었었는데 틀렸었다. 나머지 부분에서 틀린지 모르고 다른 곳에서 틀린 곳을 찾다가 나중에 깨닫고 고쳐주었다. 나머지를 구하는 문제는 중간 중간 나눠줄 것을 잊지 말자.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

string n;
int dp[5001];

void solution() {
    if (n[0] == '0') {
        cout << 0;
        return;
    }

    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n.size(); i++) {
        if (n[i - 1] != '0') {
            dp[i] = dp[i - 1];
        }

        int tmp = stoi(n.substr(i - 2, 2));
        if (tmp >= 10 && tmp <= 26) {
            dp[i] = (dp[i] + dp[i - 2]) % 1000000;
        }
    }

    cout << dp[n.size()] % 1000000;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;

    solution();

    return 0;
}