백준 1003 피보나치 함수 개념 및 풀이 (C++)

텍스트

출처 : https://www.acmicpc.net/problem/1003

기본적인 접근

처음에는 단순히 재귀함수를 사용하여 문제에서 요하는 fibonacci(0), fibonacci(1)의 횟수를 카운트하려고 했다. 하지만 문제의 포인트는 단순히 푸는 것이 아닌 '효율적인' 풀이를 원했다.내가 한 방식의 풀이는 백준에서 '시간초과'라는 메세지로 답이왔다;; 백준을 시작한지 첫날부터 코린이의 마음을 울게하는 칼같은 판정에 살짝 당황했지만 필요이상의 메모리는 낭비하는 코딩을 지양하는 백준의 철학에 수긍하는 지금이다.

서론이 길었다. 오히려 풀이는 더 간단해 질 수 있다. 피보나치 수열은 수열 그 자체로 이전값의 구 값의 합으로 이루어진 수열이다. 그리고 재귀 방식으로 푸는 피나치 코드에도 이를 결국 분할하여 가장 단순한 접근법으로 분리하는 방식을 사용한 코드를 보여 주었다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

위 코드를 간단하게 설명하자면 아래와 같다.

피보나치라 수열은 이전 수열의 두 값의 합으로 그 두 값 또한 이전 수열의 합이다. 이를 계속 따라가다 보면은 결국 초기 조건에 다다르게 된다. 그 초기조건이 바로 f(0)=1, f(1)=1이다.

이를 직관적으로 생각해보면 피보나치 수열의 값은 f(0)과 f(1)의 규칙적인 합으로 이루어 져있고 그 다음 값은 f(0)과 f(1)의 규칙적인 일련의 값의 합이라고 할 수 있다.

초기 조건 f(0)과 f(1)을 제외한 f(2)는 f(2) = f(0)+f(1) 이며 이는 2 = 1 + 1와 같다. f(3)의 경우 f(3)=f(2) + f(1) 이며 이는 3=2+1이다. 이를 다르게 쓰면 f(3) = 2f(1) + f(0)로 쓸 수 있다. 이와 같이 표현식을 정리하면 다음과 같다.

f(2) = f(1)+f(0)
f(3) = 2f(1) + f(0) = 3
f(4) = 3f(1) + 2f(0) = 5
f(5) = 5f(1) + 3f(0) = 8
f(6) = 8f(1) + 5f(0) = 13
.
.
.
위와 같이 f(0)과 f(1)의 개수 또한 피보나치 수열을 따른 다는 것을 알 수 있다.

코드

텍스트

#include <iostream>
using namespace std;
int main() {
	int testcase = 0, a = 0;
	cin >> testcase;
	int* arr;
	while (testcase--) {
		cin >> a;
		if (a < 2) {
			if (a == 0) {
				cout << "1 0" << endl;
			}
			else {
				cout << "0 1" << endl;
			}
		}
		else {
			arr = new int[41];
			arr[0] = 1, arr[1] = 1;
			for (int i = 2; i <= a; i++) {
				arr[i] = arr[i - 1]+ arr[i-2];
			}
			cout << arr[a - 2] << " " << arr[a - 1] << endl;
		}
	}
	return 0;
}

마치며

사실 처음에는 동적할당을 하여 문제를 풀려고 new int[a]를 했지만 런타임 에러 (AssertionFailed)이 나오드라 인풋에 어떤 값을 받을지 알 수 없어서 뜨는건지 정확한 이유를 모르겠다. 나중에 찾아봐야지