백준 BOJ 13022 - 늑대와 올바른 단어 [ 부제 : 참신하지만 XX같아! ]

오늘도 풀만한 문제가 없나 백준을 들락날락거리는 Koder.
매우 즐거운 문제를 발견해
아무도 상상 못할 기상천외한 방법으로 풀어보았습니다.

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

13022번: 늑대와 올바른 단어

정석인 풀이로 보자면
일일히 문자열을 비교해가며
문자의 갯수와 순서를 일일히 비교하겠지만

저는 딱 보자마자 들었던 생각이
문자열이 50자밖에 안되면
4*13 = 52이니
사실상 48글자일 것이고,

wolf에서는 다음 문자열이 두가지 갈래로 확장될 수 있습니다!
하나는 wwoollff (문자를 하나씩 더 붙임), 나머지 하나는 wolfwolf(문자열을 하나 붙임)
즉 2^13 = 8192로 시간초과는 일어나지 않기 때문에

wolf를 주어진 규칙에 맞게 조합해서 나오는 모든 문자열을 입력과 일일히 비교해보는 방법으로 소스를 작성했습니다.
진짜 변태같이 풀었네

#include <stdio.h>
#include <string.h>

char input[101] = {0};

int f(int time, int arr[], int index){
	int sum = 0;
	if(time == 13) return 0;
	char tmp[101] = {0};
	for(int i=0; i<13; i++){
		for(int j=0; j<arr[i]; j++) strcat(tmp, "w");
		for(int j=0; j<arr[i]; j++) strcat(tmp, "o");
		for(int j=0; j<arr[i]; j++) strcat(tmp, "l");
		for(int j=0; j<arr[i]; j++) strcat(tmp, "f");
	}
	if(strcmp(input, tmp) == 0) return 1;
	else{
		arr[index]++;    sum += f(time+1, arr, index);    arr[index]--;
		arr[index+1]++;  sum += f(time+1, arr, index+1);  arr[index+1]--;
	}
	return sum;
}

int main(){
	int tmp[] = {1,0,0,0,0,0,0,0,0,0,0,0,0};
	scanf("%s", input);
	printf("%d", f(1, tmp, 0));
	return 0;
} 

tmp라는 변수가 바로 이 wolf를 어떻게 조합할지를 알려줍니다

2,1,0,0.....	wwoollff + wolf
1,0,0,0.....	wolf
3,1,2,0....	wwwooolllfff + wolf + wwoollff

tmp에 들어오는 값들과 그에 해당하는 문자열의 관계입니다.
이 표로 어느정도 규칙은 이해하셨으리라 믿습니다.

이렇게 함수를 실행시키면,
함수는 가장먼저 문자열의 갯수부터 확인해서
자칫 문장이 지나치게 많이 만들어지지 않았나 확인합니다.
적당한 길이의 문장일 경우, 2중 포문을 통해 직접 문자열을 만들고,
strcmp함수를 통해 입력된 문자열과 같으면 1을 반환,
만일 다를 경우
1. 문자를 하나씩 더 추가하는 wwoollff같은 경우와
2. 뒤에 문자열을 추가하는 wolfwolf같은 경우를 나누어
다시 재귀함수를 돌립니다.

이렇게 모든 문자열을 비교해 풀어낸 결과는

크 이런맛에 플밍을 멈출수 없죠
이런 이상한 해법으로 문제를 풀어내는 재미....
짜릿해★

+ 브론즈비율이 압도적으로 높지만 슬슬 200문제를 풀어가네요....!