2011 암호코드

백준 2011 암호코드 https://www.acmicpc.net/problem/2011

A를 1. B를 2, .... Z를 26으로 암호화 할 때 수 5000자리 이하의 수 N에 대한 암호의 경우의 수를 구하는 문제이다.

처음 문제를 접했을 때는 고민하다가 결국 못풀었는데 다시 푸니 풀 수 있게됬다.
먼저 DP를 다음과 같이 정의하였다. 

$DP[N][0]$: N번째 숫자를 일의자리 숫자로 취급했을 때의 경우의 수
$DP[N][1]$: N번째 숫자를 십의자리 숫자로 취급했을 때의 경우의 수

즉 213이라는 숫자를 예로들면 
DP[3][0] : {2,1,3}, {21,3} - 2가지
DP[3][1] : {2,13} - 1가지 

먼저 $DP[N][0]$인 경우를 살펴보면 0을 제외한 숫자에 대해서는 앞의경우가 어떤경우에도 상관없음을 알 수 있다.

위의 경우에서는 {12, 3} 또는 {1, 2, 3}

0일때의  경우는 어떨까?
이때는 단독으로 0혼자만 올 수 있는 암호가 존재하지 않는다. 따라서 이 경우에 대해서는 10이나 20인 경우밖에 없기때문에 0이된다.

$DP[N][1]$인 경우에 대해 생각해 보자. 먼저 마지막 숫자를 십의 자리로 만드는 경우는 10~26밖에 없다. 이 경우는 N-1번째를 일의 자리로 올 수 있는 경우로만 해야한다.

{1, 23}

십의 자리가 안되는 경우는 당연히 그 경우가 없기에 0이다.

이걸 정리하면 점화식은 다음과같이 된다.

$if(S[N] == 0)$

         $DP[N][0] = 0$

$else$

         $DP[N][0] = DP[N-1][0]+DP[N-1][1]$

$if(10 <= S[N-1]S[N] <= 26)$

         $DP[N][1] = DP[N-1][0]$

$else$

         $DP[N][1] = 0$

#include <iostream> #define MOD 1000000 using namespace std; int dp[5001][2]; int main(){     std::ios::sync_with_stdio(false);       char str[5001];     int arr[5001];     int len;          scanf("%s", str);     for (len = 0; str[len] != NULL; len++)         arr[len + 1] = str[len] - '0';       dp[1][0] = arr[1] == 0 ? 0 : 1;     for (int n = 2; n <= len; n++){         if (arr[n] == 0)             dp[n][0] = 0;         else             dp[n][0] = dp[n - 1][0] % MOD + dp[n - 1][1] % MOD;           if ((arr[n - 1] == 1 && (arr[n] >= 0 && arr[n] <= 9)) || (arr[n - 1] == 2 && (arr[n] >= 0 && arr[n] <= 6)))             dp[n][1] = dp[n - 1][0] % MOD;         else             dp[n][1] = 0;     }     printf("%d\n", (dp[len][0] % MOD + dp[len][1] % MOD) % MOD);     return 0; } Colored by Color Scripter

cs