[BOJ] 1003. 피보나치 함수 - C++

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

 

#include <bits/stdc++.h>
using namespace std;

int z[42]; // 0 횟수
int o[42]; // 1 횟수

int main() {

	int t;

	cin >> t;
	
	for (int i = 0; i < t; i++) {
		int num;
		cin >> num;
		z[0] = 1;
		o[0] = 0;
		z[1] = 0;
		o[1] = 1;
		if (num == 0 || num == 1) {
			cout << z[num] << ' ' << o[num] << '\n';
			continue;
		}
		for (int j = 2; j <= num; j++) {
			
			z[j] = z[j - 1] + z[j - 2];
			o[j] = o[j - 1] + o[j - 2];
		}
		cout << z[num] << ' ' << o[num] << '\n';
		fill(o, o+ 42, 0);
		fill(z, z + 42, 0);
	}

}

 

#Tip

dp의 중요성은 문제를 dp인지 파악하는 것도 중요하지만

점화식을 잘 세우는 것도 중요하다.

나는 풀다가 메모지에 적어놓고 규칙들을 발견했는데 바로 j-1 j-2의 횟수를 합치게 j의 0과 1의 횟수였다.

이 문제는 dp 문제집에 놓고 dp를 인지하고 푼 문제지만 막상 실전에서는 내가 구분을 할지 모르겠다..

 

이번에 첫 코테를 보는데 기대는 없으나.. 이번 계기로 발판 삼아서 더욱 더 열심히 하는 계기가 됐으면 좋겠다.