[어려움][다이나믹 프로그래밍] 암호코드

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

암호코드 성공 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 14102 2492 1872 19.059% 문제 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러가지가 있어. 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아? 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐? 상근: 얼마나 많은데? 선영: 구해보자! 어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 5000자리 이하의 암호가 주어진다. 출력 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 예제 입력 1  25114 예제 출력 1  6

[ 문제 풀이 ]

D[i] = 왼쪽에서부터 i번째 자리까지 썼을 때, 나올 수 있는 암호의 경우의 수

D[i] = D[i-1]

만약, input[i-1]과 input[i]가 10 이상 26이하이면, D[i] = D[i-2]도 더해주어야한다.

ex) O O O O 2 5의 경우, 

D[6] = D[5]             ---> O O O O O 5 

D[6] = D[6] + D[4]    ---> O O O O 2 5

역시 D[0] = 1임에 유의한다. 경우의 수라서...

[ 최종 구현(C++) ]

#include <stdio.h>

char input[5002] = { 0 };
int D[5002] = { 0 };

int main(void)
{
	int i = 1;
	scanf("%s", input + 1);

	D[0] = 1;
	while (input[i] != '\0' && input[i] != '\n')
	{
		int x = input[i] - '0';

		if (1 <= x && x <= 9) {
			D[i] = (D[i] + D[i - 1]) % 1000000;
		}

		if (i == 1) { i++;  continue; }
		if (input[i - 1] == '0') { i++;  continue; }

		x = (input[i - 1] - '0') * 10 + (input[i] - '0');

		if (10 <= x && x <= 26)
		{
			D[i] = (D[i] + D[i - 2]) % 1000000;
		}

		i++;
	}

	printf("%d\n", D[i - 1]);

	return 0;
}