[C] 백준 1003번: 피보나치 함수

 언뜻 쉬워보이는 문제이지만 함정이다. 피보나치 함수를 그대로 줘서 마치 저걸 변형하면 되게 보이게 했지만 완전히 다른 방법으로 접근해야 한다. 문제 조건의 제한 시간은 0.25초. 시간복잡도 O(n)으로 맞춰야 풀 수 있다.

입출력 예시

정답코드

#include <stdio.h>

typedef struct fibo {

	int zero_count;
	int one_count;

}FIBO;

FIBO f[41] = { {0, 0} };

FIBO CountZeroOne(int);

int main(){

	int T;

	int i;
	int n;

	f[0].zero_count = 1;
	f[0].one_count = 0;

	f[1].zero_count = 0;
	f[1].one_count = 1;

	scanf("%d", &T);

	CountZeroOne(40);

	for (i = 0; i < T; i++) {
		scanf("%d", &n);

		printf("%d %d\n", f[n].zero_count, f[n].one_count);
	}

	return 0;

}

FIBO CountZeroOne(int n) {

	FIBO tmp, tmp2;

	if (f[n].zero_count == 0 && f[n].one_count == 0) {

		tmp = CountZeroOne(n - 1);
		tmp2 = CountZeroOne(n - 2);
		f[n].zero_count += tmp.zero_count + tmp2.zero_count;
		f[n].one_count += tmp.one_count + tmp2.one_count;

	}

	return f[n];
}

코드설명

0. 시작 전에, 동적 계획법 메모이제이션 방법을 사용할 것이다. 메모리를 더 써서 연산 시간을 확 줄이는 것이다.

1. FIBO라는 구조체를 만든다. 여기에는 n번째 피보나치 수열이 0, 1을 몇번 출력하는지 저장할 것이다. 구조체 FIBO를 41개 짜리 배열 전역변수로 선언한다. 이 때, 모두 0으로 초기화 시켜준다.

2. f의 0번째와 1번째는 각각 0이 1번, 1이 1번 출력되므로 맞게 설정시켜준다.

3. CountZeroOne 함수는 다음과 같다. 만약 f의 n번째 두 개 변수가 모두 0이면 저장되지 않은 것이므로 재귀를 통해 계산을 한다. 피보나치 함수의 그것과 같다. 대신 여기서는 0의 갯수와 1의 갯수만 더해준다.

4. CountZeroOne(40)을 실행한다. 그러면 그러면 40부터 0까지 연산을 하기때문에 배열에 다 채워진다.

5. T를 입력받고 T개의 n을 입력받고 해당하는 답을 출력한다