[BOJ] 2011번. 암호코드

www.acmicpc.net/problem/2011

2011번: 암호코드

고생 많으셨어요! DP문제들을 너무 잘 풀어주셔서 살짝 어려운 문제들을 내봤습니다. 근데 너무 어려웠던 것 같아요.... 저도 다시 푸려니까 어렵더라구요... 죄송합니다...

그럼 풀이 바로 시작하겠습니다!

[정답 코드 보기]

#include <iostream>
#include <string.h>
#define mod 1000000;
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	string str;
	int dp[5001] = { 0, },length;
	dp[0] = 1;
	
	cin >> str;
	length = str.length();
	str = '0' + str;
	for (int i = 1; i <= length; i++)
	{
		int x = str[i] - '0';
		if (1 <= x && x <= 9)
		{
			dp[i] = (dp[i] + dp[i - 1]) % mod;
		}
		if (i == 1) continue;
		if (str[i - 1] == '0') continue;
		x = (str[i - 1] - '0') * 10 + (str[i] - '0');
		if (10 <= x && x <= 26)
		{
			dp[i] = (dp[i] + dp[i - 2]) % mod;
		}
	}
		cout << dp[length];
		return 0;
}

[코드 설명 보기]

역시 이 문제도 정답의 크기를 감당할 수 없었는지 1000000으로 나눈 나머지 숫자를 출력하라네요!

0의 갯수가 많아 일일히 적기 귀찮으니 mod로 선언해줍니다. 또한 여기서 사용할 변수들도 선언해줬어요!

#include <iostream>
#include <string.h>
#define mod 1000000;
using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
	string str;
	int dp[5001] = { 0, },length;
	dp[0] = 1;

제가 하고 싶은 것은 다음과 같습니다.

입력으로 25114가 들어 왔습니다.

for문을 통해서 하나하나 비교하며 정답을 찾아갈 것입니다.

비교를 위해, 맨 앞에 0을 추가하였습니다.

cin >> str;
length = str.length();
str = '0' + str;

str.length()함수를 통해 str의 길이를 구할 수 있습니다. 

str 앞에 '0'을 추가한 상태이므로 현재 str은 "025114"입니다.

 

우선 for문을 통해 현재 검색하고 있는 숫자는 알파벳으로 몇번째 자리수인지 확인해 보겠습니다.

예를 들어, 1을 알파벳으로 바꾸면 A, 2를 알파벳으로 나누면 B, ... 26을 알파벳으로 바꾸면 Z일 것입니다. 

for (int i = 1; i <= length; i++)
	{
		int x = str[i] - '0';
		if (1 <= x && x <= 9)
		{
			dp[i] = (dp[i] + dp[i - 1]) % mod;
		}

우리는 25114중 인덱스가 1인 '2'부터 탐색하고 있습니다. 따라서 '2'-'0'을 하면 아스키 코드에서 82-80을 한 것과 같으므로 x는 2가 될 것입니다.

 DP부분을 살펴보겠습니다.

 

만약 숫자가 37이었다면, 이 숫자는 037로 변경됩니다.

DP[0]은 1로 초기화 해주고, 탐색은 1부터 시작합니다.

 

for문에서 i가 1일때, DP는 다음과 같이 초기화 될 것입니다.

  dp={1, 1, 0}

for문에서 i가 2일때, DP는 다음과 같이 초기화 될 것입니다.

  dp={1, 1, 1}

생각해보면 자명합니다. 3은 C로 치환될 수 있고, 7은 G로 치환될 수 있으나, 37에 해당되는 알파벳은 없으니까요.

그런데, 25114는 어떤가요??

25114는 역시 025114로 변경되고, DP[0]은 1로 초기화되어있습니다.

 

for문에서 i가 1일때, DP는 다음과 같이 초기화 될 것입니다.

  dp={1, 1, 0, 0, 0, 0}

for문에서 i가 2일때, DP는 다음과 같이 초기화 될 것입니다.

   dp={1, 1, 1, 0, 0, 0}

엇 근데.... 2는 B로, 5는 E로 치환될 수 있고, 25 역시 Y로 치환될 수 있습니다.

따라서, 다음과 같은 부분을 추가해 줍니다.

for (int i = 1; i <= length; i++)
	{
		int x = str[i] - '0';
		if (1 <= x && x <= 9)
		{
			dp[i] = (dp[i] + dp[i - 1]) % mod;
		}
		if (i == 1) continue;
		if (str[i - 1] == '0') continue;
		x = (str[i - 1] - '0') * 10 + (str[i] - '0');
		if (10 <= x && x <= 26)
		{
			dp[i] = (dp[i] + dp[i - 2]) % mod;
		}
	}

코드보니까 동공이 흔들리시진 않나요?? 전 항상 그래요... 하지만!! 제가 잘 설명해드릴게요.

i가 1인 경우에는 맨 처음 부분이니까 넘어가 주었습니다.

i-1, 그러니까 지금 보고있는 숫자 바로 앞 부분이 0이었다면, 볼것도 없죠!! 넘어가줍니다(10이나 20은 미리 처리해줍니다! 그러니까 이 부분은 01혹은 08같이 생긴 알파벳은 넘어간다는 의미입니다.)

 

이제부터가 좀 중요합니다.

앞의 관문을 통과한 숫자는 일단 쓸모가 좀 있을 것 입니다.

앞의 숫자에 10을 곱하고, 현재 숫자를 더해주면!! 앞과 현재 숫자가 더해진 수가 X가 됩니다.

그림과 함께 살펴보죠!!

이제 우리가 구한 숫자가 알파벳 범위, 그러니까 1~26사이에 속하는지 확인해 줍니다.

만약 이 범위 내부에 속하는 것이 확인 되면 DP를 수정합니다.

바로 앞의 숫자는 같은 알파벳 범위의 10의자리 수에 속하므로 앞앞의 DP에 현재 DP를 더해주도록 합시다.

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

그럼 마지막 자리에는, 전체 암호의 길이가 저장되어져 있을 것 입니다.

	cout << dp[length];
	return 0;
}