[C/C++] 백준 - 2011번 : 암호코드

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

2011번: 암호코드

문제

상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.

• 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.
• 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.
• 상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?
• 선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데, 그걸 언제 다해봐?
• 상근: 얼마나 많은데?
• 선영: 구해보자!

어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 구하는 프로그램을 작성하시오.

 

 

난 DP 문제가 제일 어렵다. 근데 또 풀리면 기분은 제일 문제 ,,

종만북의 원주율 구하기 문제를 공부한 후 비슷한 문제를 찾다가 이 문제를 골라 풀게 되었는데

조금 시간 걸린 문제

 

난 이 문제의 접근 방식을

 

1. 재귀를 이용한 완전탐색 알고리즘을 먼저 구현한 후 

2. 메모이제이션을 적용하였다.

3. 재귀를 이용하게 되면 시작지점부터 끝지점까지 방문한 후 되돌아오는 과정을 거치기에 앞서 해결한 부분은 다시 확인할 필요없이 값만 가져오면 된다.

 

재귀를 구현할 때 기저사례는

1. 해당 위치의 값이 0인 경우 아무 알파벳과 매칭을 할 수 없기에 0을 반환해준다.

2. 해당 위치가 문자열의 길이와 일치할 경우 재귀를 통해 끝위치까지 온 경우 -> 즉 1개는 생성했으므로 1 반환

 

그리고 재귀함수를 수행하는 경우는 크게 2가지로 나누어주었다.

1. 현재 위치의 값이 알파벳(1~26)과 매칭이 가능한 경우 바로 다음 위치로 재귀함수 실행

2. 현재 위치+다음 위치를 이어붙인 값이 알파벳(1~26)과 매칭이 가능한 경우 2칸 뛴 다음 위치로 재귀함수 실행

 

위와 같이 구현해주면 이미 개수를 센 위치 값을 방문하게 되면 값만 반환하여 빠르게 해결할 수 있다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 

#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

string N;
ll cache[5003];

ll solution(int begin) {
    if(N[begin]-'0' == 0) return 0;
	if (begin == N.size()) return 1;
	ll& ret = cache[begin];
	if (ret != -1) return ret;

	ret = 0;
	if (begin + 1 <= N.size() && 1 <= stoi(N.substr(begin, 1)) && stoi(N.substr(begin, 1)) <= 26) {
		ret = (ret + solution(begin + 1)) % Mod;
	}
	if (begin + 2 <= N.size() && 1 <= stoi(N.substr(begin, 2)) && stoi(N.substr(begin, 2)) <= 26) {
		ret = (ret + solution(begin + 2)) % Mod;
	}
	return ret;
}

void input() {
	cin >> N;
	ll answer = 0;
	memset(cache, -1, sizeof(cache));
	if (N[0] != '0') answer = solution(0);
	cout << answer << endl;
}

int main() {
	fastio;
	input();
	 
	return 0;
}