C++) 백준 2011번 풀이_암호코드

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

2011번: 암호코드

 

문제 풀때 정답률을 딱히 살피지 않고 푸는 편인데

그랬어서 다행이다... ^^ 다시보니 19퍼센트네;; 도전도 안 했을듯

 

이게 그냥 보면 그냥... 앞에서부터 세어나가면 될 것 같은데

0이 들어가는 경우의 예외처리때문에 좀 생각이 복잡해졌다

 

테스트케이스 25114에서 대충 돌아가는 꼴을 보면

 

이렇게 증가하고,

그래서 이걸 간단하게 나타내보면

i-1자리랑 i자리랑 합쳐서 27보다 작으면

D[i] = D[i-1] + D[i-2]

해주고, 그 경우가 아니라면

D[i] = D[i-1]

그대로 내려오면 되는...듯해보이지만

 

 

0이 들어간다면?

 

인풋에 0이 들어가지 않을 거라고 지정되어 있는 것도 아니고,

심지어  암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. 라고 친절하게 명시도 해두셨다.

 

그러므로 우리가 걸러야 할 경우를 간단하게 생각해보면

 

0

50

100

 

이 경우에는 절대 0이 나오고,

109는 1개밖에 안된다. 10, 9

 

 

일단 걸러야 하는게 

인풋으로 0만 들어올 때,

중간에 0이 들어왓는데 앞 자리랑 합쳐서 10이나 20이 안 될 때.

돼서 넘어왔는데 다음이 0일때,

 

뭐 이런...

 

근데 이걸 결국 한번 더 걸러서 생각해보면

 

받은 수가 0보다 클 때 -> 앞의 자리수와 합쳐서 검사 안 해도 되니까 i-1을 더한다.

받은 수와 앞자리를 합쳐서 10보다 크고 26보다 작다 -> 앞의 자리수랑 합쳐서 생각해야되니까 i-2를 더한다

-> 두가지 모두 만족하지 못할 경우는 즉시 계산을 종료한다.

 

정도로 짜볼 수 있겠습니다~~~

이래저래 정리해서.. 코드를 짜면 됩니다.

더러워서 맘에 안들지만... 더 생각하기 싫었다.

 

#include<stdio.h>

int main(void) {
	int cnt;
	int pass[5001][2] = { 0, };

	scanf("%1d", &pass[1][0]);
	cnt = 1;

	if (pass[1][0] != 0)
	{
		pass[1][1] = 1;
		pass[0][1] = 1;
	}

	while(scanf("%1d", &pass[++cnt][0]) != EOF)
	{
		if (pass[cnt][0] > 0)
		{
			pass[cnt][1] = pass[cnt - 1][1];
		}

		if (pass[cnt - 1][0] * 10 + pass[cnt][0] < 27 &&
			pass[cnt - 1][0] * 10 + pass[cnt][0] >= 10)
		{
			pass[cnt][1] += pass[cnt - 2][1];
		}

		pass[cnt][1] %= 1000000;

		if (pass[cnt][1] == 0)
		{
			cnt++;
			break;
		}

	}

	printf("%d", pass[cnt-1][1]);
}