[2011번] 암호코드

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

DP 점화식 적용을 잘못해서 한참 고생하던 문제이다.

점화식은 다음과 같다.

1. 현재 보고있느 값이 0이 아니면 dp[i] = dp[i-1]이다.

2. 이전값이 10~19 이거나 20~26사이 수이면 dp[i] += dp[i-2]를 해주면 된다.

이 이유는 i-1 값과 i값에 의해 결정되므로 결국 dp[i-2]에 있는 값이 모든 암호의 수가 된다. 

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <string.h>
 
using namespace std;
 
const long long MOD = 1000000;
 
long long dp[5003];
char str[5003];
 
int main()
{
        scanf("%s", str + 1);
 
        int len = strlen(str + 1);
 
        if (str[1] == '0')
        {
            printf("0");
            return 0;
        }
 
        dp[0] = dp[1] = 1;
 
        for (int i = 2; i <= len; i++)
        {
            if (str[i] != '0')
                dp[i] = dp[i - 1] % MOD;
 
            if(str[i - 1] == '1' || str[i - 1] == '2' && str[i] <= '6')
                dp[i] += dp[i - 2] % MOD;
        }
 
        printf("%lld\n", dp[len] % MOD);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>