[백준 2011번] 암호코드 (C++)

문제링크 : https://www.acmicpc.net/problem/2011

2011번: 암호코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

string s;
const int MOD = 1000000;
int dp[5001];

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

    cin >> s;
    dp[0]=dp[1]=1;

    for(int i=2; i<=s.size(); i++)
    {
        int tmp1 = s[i-1]-'0'; //한 자리 숫자로 변환
        if(tmp1>=1 && tmp1<=9) dp[i] = (dp[i] + dp[i-1]) % MOD;
        int tmp2 = (s[i-2]-'0') * 10 + (s[i-1]-'0'); //두 자리 숫자로 변환
        if(tmp2>=10 && tmp2<=26) dp[i] = (dp[i] + dp[i-2]) % MOD;
    }
    
    cout << (s[0]=='0' ? 0 : dp[s.size()]);
    
    return 0;
}

DP 문제이다.

문저 규칙을 살펴보면 다음과 같다.

<2 5 1 1 4>
- 두 자릿수가 가능한가 아닌가에 따라 나뉨

2 : B

5 
 - 25 : BE
 - 5 : Y
 
1 : BEA, YA

1 
 - 11 : BEK, YK
 - 1 : BEAA, YAA
 
4
 - 14 : BEAD, YAD
 - 4 : BEAAD, YAAD, BEKD, YKD
 
 한 자릿수의 경우 -> dp[n] = dp[n-1]
 두 자릿수의 경우 -> dp[n] = dp[n-2]

 

위와 같이 현재수와 직전 수를 합쳐 만든 두자릿수가 10이상이고 26이하일 때와 아닐때로 경우의 수가 갈린다.

따라서 임시변수를 2개 만들어 한 자릿수 용과 두 자릿수 용으로 사용하였다.

한 자릿수일때 1<=tmp<=9라면 (0이 아니라면) 무사히 변환이 이루어지므로 dp[i] += dp[i-1]이 된다.

두 자릿수일때 10<=tmp<=26이라면 dp[i] += dp[i-2]이 된다.

두 자릿수의 경우 직접 직전수 * 10 + 현재수를 하여 만들어주어야 한다.

 

주의해야 할 점은 처음 시작 부분이다.

예제의 첫 시작은 무조건 한자릿수이므로 dp도 마찬가지로 1로 초기화해준다.

그 다음 숫자가 문제인데, 만들어진 두 자릿수가 조건을 통과할때 dp[i] += dp[i-2]를 해주었으나, 

i=1이 5인 경우에는 (두 자릿수 : 25) 위 dp 식 계산이 불가능하기 때문이다.

이를 위해서 dp를 dp[1]까지 1로 초기화를 해주어서 앞 2칸을 확보해주고 이에 맞춰서 i를 조절하여 계산해주어야 한다.

 

따라서 반복문은 i=2부터 시작되는데 s[i]로 탐색을 하면 의도했던 5부터 시작이 아닌 1부터 시작하게 된다 (25114)

그래서 s[i]가 아닌 s[i-1]로 주어서 인덱스를 조절해주어야 한다.

dp의 i는 의도한게 맞으므로 그대로 i로 넣어주면 된다.

 

마지막으로 출력할 때 해석할 수 없는 경우는 0을 출력하도록 했다는 것을 주의해야한다.

이 경우는 맨 앞에 숫자가 0이 오는 경우로 출력시에 이를 예외처리를 해주어야한다.