[알고리즘] C++ 백준 2011 암호코드

백준 2011

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

2011번: 암호코드

풀이 전 나의 생각

주어진 숫자를  1 = A , 2 = B... 의 조건으로 암호화해야 한다. 하지만 숫자를 암호화 했을 때 글자로 바꾸는

방법이 여러가지기 때문에 모든 경우의 수를 구해야 한다.

 

우선 문제에서 나온 예시인 25114를 사용하여 각 상황에 어떤 암호가 나오는지 판별해보자.

 

2 = B

25 = BE, Y
251 = BEA, YA
2511 = BEAA, YAA, YK, BEK

 

(2) -> 숫자가 하나인 부분은 1부터 9사이의 숫자라면 암호가 한개 생성된다.

 

(25) -> 뭔가 (2)의 B에서 추가적으로 값을 붙여서 나온 값이 BE인 것 같다. 하지만 아직까진 확실하진 않다.

그리고 25는 1이상 26이하의 숫자이기 때문에 알파벳으로 한번 더 바뀔 수 있다. 그러므로 암호가 두 개 생성된다.

 

(251) ->  (25)의 BE, Y에 추가적으로 값이 붙어서 BEA, YA가 된 것으로 보인다. 하지만 51부분이 26을 초과하기 

때문에 더 이상 추가되는 값이 없어 암호가 두 개 생성된다.

 

(2511) ->  (251)의 BEA, YA에 추가적으로 값이 붙어서 BEAA, YAA가 된 것으로 보인다. 근데 전과 달리 11부분에서

알파벳으로 변환이 가능하기 때문에 YK, BEK란 암호가 추가적으로 생겼다. 이는 (2511)에서 11을 제거한 숫자 

(25)에서 11의 변환 값을 붙여준 것으로 보인다.

 

여기서 알 수 있는 정보는 현재 비교하고 있는 숫자가 1에서 9사이의 값이라면 어떻게든 이전의 값은 들고온다.

그리고 추가적으로 현재 비교하고 있는 위치의 숫자를 10의 자리까지 비교했을 때 10이상 26이하의 수라면

2회 이전의 값을 들고온다.

 

그럼 이를 점화식으로 표현하면

1. (숫자가 1이상 9이하 일 때) DP[N] = DP[N] + DP[N - 1]

 

2. (현재 위치의 10의 자리 수가 10이상 26이하 일 때) DP[N] = DP[N] + DP[N - 2]

 

추가적인 조건으로 암호가 되지 않으면 0을 출력하라고 나와있다.

암호가 되지 않는 조건은

1. 0이 먼저 앞에 나왔을 때 -> 처음 입력 값을 받을 때 암호의 첫 글자가 0이면 0을 출력해주고 종료한다.

2. 10, 20이 아닌 30, 40... 이 나왔을 때 -> 2번 점화식에서 걸러진다.

3. 100, 2000..., 0이 여러개 나왔을 때 -> 1번 점화식에서 걸러진다.

 

그리고 1000000을 나누면서 값을 얻어야 하는 것을 잊지말자.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>

using namespace std;

int code_arr[5001];
int dp[5001];
#define MOD 1000000
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string code;
	cin >> code;

	for (int i = 1; i <= code.length(); i++)
	{
		code_arr[i] = code[i - 1] - '0';
	}

	if (code_arr[1] == 0)
	{
		cout << 0;
		return 0;
	}

	dp[0] = 1;

	for (int i = 1; i <= code.length(); i++)
	{
		if (code_arr[i] >= 1 && code_arr[i] <= 9)
		{
			dp[i] = (dp[i - 1] + dp[i]) % MOD;
		}

		if (i == 1) continue;
		int tmp = (code_arr[i - 1] * 10) + code_arr[i];

		if (tmp >= 10 && tmp <= 26)
		{
			dp[i] = (dp[i - 2] + dp[i]) % MOD;
		}

	}

	cout << dp[code.length()];
}