(c++)백준 2011번: 암호코드

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

2011번: 암호코드

입력에 뛰어쓰기가 없고, 몇 자리수인지도 알려주지 않기 때문에 먼저 string으로 암호를 입력 받은 뒤에 int형 배열에 형변환 시켜 저장하는 방법을 썼다.

※점화식※

dp[i] : i번째 숫자까지 봤을 때 읽을 수 있는 단어의 개수

두 가지 경우가 있다.

1. i번째 숫자를 한자리 수로 따로 읽는 경우: dp[i] = dp[i-1]+dp[i] (조건:Code_Num[i]가 0이 아닌 한자리 자연수여야 한다.)

2. i-1번째 숫자와 i번째 숫자를 두자리 수로 함께 읽는 경우: dp[i] = dp[i-2]+dp[i] (조건:Code_Num[i-1]*10+Code_Num[i]가 10~26사이(알파벳)의 두자리 자연수여야 한다.)

*이때 dp[0]은 dp[1]의 첫번째 경우를 구하기 위해 1로 초기화 되어있어야 한다.

∵ 한자리 수에서 첫번째 숫자를 한자리 수로 따로 읽는 경우는 1가지 이므로! (dp[i]는 모두 0으로 초기화 되어있다.)

 

#include <iostream>
#include <string>
using namespace std;
#define D 1000000

int N;//자릿수
string Code_str;
int Code_num[5001];
int dp[5001];

//string으로 받은 암호를 int로 저장
void getNum() {
	N = Code_str.size();
	for (int i = 0; i < N; i++) {
		Code_num[i + 1] = Code_str[i] - '0';
	}
}

void DP() {
	//암호가 잘못된 경우
	if (N == 1 && Code_num[1] == 0) {
		cout << 0 << endl;
		return;
	}

	dp[0] = 1;
	for (int i = 1; i <= N; i++) {
		//마지막 숫자가 0이 아닌 한자리 자연수면
		if (Code_num[i] >= 1 && Code_num[i] <= 9) {
			//마지막 숫자를 한 글자로 보는 경우
			dp[i] += dp[i - 1] % D;
		}
		//(i-1번째 숫자) * 10 + i번째 숫자가 두자리 자연수이고 알파벳 범위 안에 있으면
		if (Code_num[i - 1] != 0 && (Code_num[i - 1] * 10 + Code_num[i]) >= 10 && Code_num[i - 1] * 10 + Code_num[i] <= 26) {
			//i-1번째 숫자와 i번째 숫자를 하나의 두 자리 자연수로 보는 경우
			dp[i] += dp[i - 2] % D;
		}
	}
	cout << dp[N] % D << endl;
}

int main() {
	cin >> Code_str;
	getNum();
	DP();
	return 0;
}