[Week 1] BOJ #1003 self review - hanjuuuuuu

[hanjuuuuuu]

self review

• 파일명: 1003FIBO.cpp (branch:hanjuuuuuu)
• 수행시간: 4ms

1. 문제 해결 과정

처음에는 그냥 피보나치 함수와 같은 특징이라고 생각해서 단순히 재귀함수로만 구현했더니 시간초과가 나왔다.
시간을 줄일 수 있는 방법을 생각하다 메모이제이션을 이용하기로 하였다.

2. 아이디어

메모이제이션을 0으로 초기화해준 뒤 입력받는 n의 자리에 각각의 값을 저장해준다.
n이 0일 경우는 0이 한번 출력되므로 1 0이 출력되어야 하는데, n이 -1일경우는 메모이제이션을 사용할 수 없으므로
예외처리를 해준다.

3. 코드 설명

#include <iostream>
#include <cstring>
using namespace std;

int T, N;
int memo[50];

int fibo(int n) {
	if (n == 0) {
		memo[0] = 0;
		return 0;
		
	}
	else if (n == 1) {
		memo[1] = 1;
		return 1;
		
	}

	if(memo[n] == 0) {
		memo[n] = fibo(n - 2) + fibo(n - 1);
		return memo[n];
	}

	return memo[n];
	
}

	int main(){
		memset(memo, 0, sizeof(memo));
		cin >> T;
		for(int i = 0; i < T; i++) {
			cin >> N;
			
			if (N == 0) {
				cout << "1 0" << endl;
			}
			else {
				fibo(N);
				cout << memo[N-1] << " " << memo[N] << endl;
			}
			
		}
		return 0;
	}