BOJ 2011번 암호코드

BOJ : https://www.acmicpc.net/problem/2011

github : https://github.com/junho0956/Algorithm/blob/master/2011/2011/%EC%86%8C%EC%8A%A4.cpp

 

경우의 수를 되짚어보겠습니다.

 

1) 현재 수가 0 초과일때 => 무조건 한자리 수는 만들 수 있습니다.

이게 의미하는 것은 결국 가짓수에 변화가 없다는 뜻입니다.

ex ) ...23을 읽고 있을 때 2와 3을 기준 한자리 수가 의미하는 것은 BC 를 만드는 것이라는 뜻입니다.

 

2) 현재 수와 직전의 수를 합했을 때의 범위를 봅시다

현재수 + 직전의수*10 이 만약 10이상 26이하라면

현재수-2까지 만들수 있는 가짓수에다가 새로운 가짓수가 생긴 것입니다.

ex ) ...323을 읽고 있을 때 그 수는 23이 되고, 이의 경우 CB3 => CBC 또는 C에 새로운가짓수 23인 W가 되어 CW 

 

이렇게까지만해서 제출했더니 WA를 받았습니다.

게시판을 보니 앞자리에 0이 나올 수 있다고 하더라구요... 그래서 그 부분만 처리해줬더니 AC를 받았습니다

 

dp[0] = dp[1] = 1 을 해준 이유는,

직접 해보시면 알겠지만 최소한 맨앞이 0이 아니라면

무슨 숫자든 1가지의 경우는 만들 수 있다는 뜻입니다.

그리고 저는 for문을 string의 2번째인자부터 읽었기 때문입니다. 그래서 str[i-1]을 사용한 것이구요

그렇기때문에 첫 인자인 1을 읽을 때 else에 대해 범위를 벗어나지 않기위해 2개를 동시에 1이라고 초기화한 것 입니다.

 

#include <iostream>
#include <string>
using namespace std;
#define MOD 1000000
 
int dp[5001];
string str;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> str;
 
    if (str[0] == '0') {
        cout << "0";
        return 0;
    }
    else {
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= str.length(); i++) {
            if (str[i-1] - '0' > 0) {
                dp[i] = dp[i - 1] % MOD;
            }
            int num = (str[i-1] - '0') + (str[i - 2] - '0') * 10;
            if (num > 9 && num < 27) {
                dp[i] = (dp[i] + dp[i - 2]) % MOD;
            }
        }
 
        cout << dp[str.length()];
    }
    return 0;
}