[boj][c++] 1003 피보나치함수, 1904 01타일

1003 피보나치 함수

어제 자기 전에 dp문제 풀고나서 감이 좀 잡히는 느낌이라 다른 dp문제 골라서 풀어봤다. 그냥 피보나치 수열 구하는게 아니고 0과 1이 몇번 쓰였는지 알아내야 해서 식 자체는 무척 간단했고, 풀이를 dp로 도출해내면 된다는 힌트를 알고 있었기 때문에 쉽게 풀었다.

0	1	2	3	4
1, 0	0, 1	1, 1	1, 2	2, 3

위의 표는 f(n)일 때 각각 0과 1이 몇 번 출력되는지 정리한 표이다. 피보나치 수열의 원리는 f(n)=f(n-1)+f(n-2)(단, n은 2 이상) 이라는 명확한 점화식이 존재한다. f(n-1)에서의 0과 1의 출력 갯수, f(n-2)에서의 0과 1의 출력 갯수를 더하면 된다.
따라서 문제에서 제시된 n의 범위인 0부터 40까지의 수열에 각각 0의 갯수와 1의 갯수를 저장할 배열을 만들어서 값을 미리 저장한다. 그 다음 n의 값을 반복해서 입력받으며 n번째 인덱스에 저장된 값을 출력하면 된다.

점화식이 워낙 유명한 문제라서 쉽게 풀린 것도 있지만... 뿌듯하다! vector+fair로 받으면 코드가 더 간결해질 것 같다.

#include	<iostream>
using namespace std;

int dp_zero[41];
int dp_one[41];

int main()
{
	dp_zero[0] = 1;
	dp_one[0] = 0;
	dp_zero[1] = 0;
	dp_one[1] = 1;
	int t, n;
	cin >> t;
	for (int i = 2; i <= 40; i++)
	{
		dp_zero[i] = dp_zero[i - 1] + dp_zero[i - 2];
		dp_one[i] = dp_one[i - 1] + dp_one[i - 2];
	}
	for (int i = 0; i < t; i++)
	{
		cin >> n;
		cout << dp_zero[n] << " " << dp_one[n] << "\n";
	}
	return 0;
}

---

1904 01타일

dp 감 잡은 김에 더 풀어보려고 고른 문제. 그런데 점화식 세우려고 표 만들다보니 뭔가 익숙한 느낌의 수열...이...!

1	2	3	4	5	6
1	2	3	5	8	13

ㅋㅋㅋㅋ바로 윗 문제가 피보나치 수열에서 f(1), f(0)의 횟수 구하기였는데 이 문제는 그냥 피보나치 수열 그 자체였다. 처음에 어렵게 생각하고 접근했는데 막상 표 만드니까 약간 기운빠진다. 식은 쉽게 세웠다.

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

vector<long long int> tile(1000001);

int main()
{
	int n;
	cin >> n;
	tile[1] = 1;
	tile[2] = 2;
	tile[3] = 3;
	for (long long int i = 4; i <= n; i++)
	{
		tile[i] = (tile[i - 1] + tile[i - 2]) % 15746;
	}
	cout << tile[n] << "\n";
	return 0;
}