BOJ 2011 | 암호코드

🔗 문제 링크

문제 스택	문제 번호	언어
BOJ	2011	C99

🔑 풀이

메모이제이션을 사용했으므로, DP로 풀었다고도 볼 수 있지만,

이중배열로 담는 것으로 논리를 쪼개는 것이 편하다보니 3의 너비를 가지는 이중배열을 할당

mem[i][0] 에는 기존의 값, 누적된 모든 경우의 수를 표시

mem[i][1] 에는 각각의 수가 독립되는 경우의 수를 표시

mem[i][2] 에는 알파벳 넘버링으로 10 ~ 26이 되는 경우(이하 , 연속된 두개의 수가 하나의 수로 여겨지는 경우의 수를 표시

예제인 25114 의 경우를 생각해본다.

• index : 1
  • mem[1][1] 직전의 mem[0][1] 이 없기도 하거니와, 직전의 메모이제이션이 없기 때문에, 연속되는 수가 될 수 없기에 1이 된다.
  • mem[1][2] 에는 알파벳 넘버링으로 10 ~ 26(이하 연속수)이 되는 경우인데, 마찬가지로 직전의 요소가 없기 때문에 0이 된다.
• index : 2
  • 25가 되므로, 그림에서 처럼 2, 5 혹은 25 이렇게 두가지 경우로 분기한다.
  • mem[2][1] : 2, 5 를 나타내므로 1.
  • mem[2][2] : 25 를 나타내므로 1.
  • mem[2][0] : 합이 2가 된다.
• index : 3
  • 앞의 수가 5, 현재 수가 1이므로, 연속수가 오지 않는다.
  • mem[3][1] : 2.
  • mem[3][2] : 0
  • mem[3][0] : 합이 2가 된다.
• index : 4
  • 앞의 수가 1, 현재 수가 1이므로, 연속수로도 경우의 수를 확장할 수 있으므로,
  • mem[4][1] : 2
  • mem[4][2] : 2
  • mem[4][0] : 합이 4가 된다.
• index : 5
  • 앞의 수가 1, 현재 수가 4이다. 여기서 중요한다.
  • mem[5][1] : 직전의 모든 경우의 수는 독립된 수 4가 이어올 수 있으므로 4가 된다.
  • mem[5][2] : 직전의 모든 경우의 수를 가져올 수는 없다. 3연속된 수가 될 수도 있기 때문에, 직전의 독립수인 mem[4][0] 을 가져와 독립수 4를 붙혀주어 2가 된다.
  • mem[5][0] : 합이 6이 된다.

정답률이 20%가 안되는 것은

이 문제는 어렵다기 보다는

생각보다 까다로운 예외사항 때문에 정답률이 낮은 편이다.

이런 문제를 현실에서 만난다면 얼마나 까다로울지 상상이 가지 않는다(현실에는 답지가 없기 때문이다).

• 0 -> 0 (0이 가장 앞자리에 온다면 불가능한 수이다.)
• 9 -> 1
• 10 -> 1
• 11 -> 2
• 26 -> 2
• 27 -> 1
• 99 -> 1
• 100 -> 0 (0이 2개 연속으로 오는 경우 불가능한 수이다.)
• 1010 -> 1 (0으로 끝나는 연속수인 경우 하나의 수로 보아야 한다.)
• 1011 -> 2
• 1020 -> 1
• 1030 -> 0 (0으로 끝난다 하더라도 10, 20이 아닌 수는 불가능한 수이다.)
• 1203 -> 1

• 가장 많이 하는 실수는
  • [10, 26] 범위가 아닌 [10~30] 으로 처리하는 경우.
  • 위 예시처럼 0에 대한 예시 불가능 처리를 잘못 하는 경우.
    • 0이 들어온 불가능한 경우
    • 0이 연속으로 오는 불가능한 경우
    • 0으로 끝나는 연속수에 대한 점화식 처리
    • 0으로 끝난다 하더라도 불가능한 경우

📝 코드

#include <stdio.h>

int		ft_error(void)
{
	printf("0");
	return (0);
}

int		main(void)
{
	char	s[5001] = {0};
	int		mem[5001][3] = {0};
	int		i;

	scanf("%s", s);
	if (s[0] == '0')
		return (ft_error());
	mem[0][0] = 1;
	mem[0][1] = 1;
	i = 1;
	while (s[i])
	{
		if ((s[i - 1] != '1' && s[i - 1] != '2') && s[i] == '0')
			return (ft_error());
		if ((s[i - 1] == '1' && '0' == s[i]) ||
					(s[i - 1] == '2' && '0' == s[i]))
		{
			mem[i][1] = mem[i - 2][0];
			mem[i][2] = 0;
			mem[i][0] = mem[i - 1][1] % 1000000;
		}
		else if ((s[i - 1] == '1' && ('0' <= s[i] && s[i] <= '9')) ||
					(s[i - 1] == '2' && ('0'<= s[i] && s[i] <= '6')))
		{
			mem[i][1] = mem[i - 1][0];
			mem[i][2] = mem[i - 1][1];
			mem[i][0] = (mem[i][1] + mem[i][2]) % 1000000;
		}
		else
		{
			mem[i][1] = mem[i - 1][0];
			mem[i][2] = 0;
			mem[i][0] = mem[i][1] % 1000000;
		}
		i++;
	}

	printf("%d", mem[i - 1][0] % 1000000);
	return (0);
}