백준 1904 - 01타일

문제 번호: 1904

문제 제목: 01타일

문제 주소: https://www.acmicpc.net/problem/1904

문제 내용

00과 1을 조합하여 표현할 수 있는 글자 N개의 가짓수를 출력한다.

테스트 케이스

1	1
2	2
4	5
7	21
1000000	7871

문제 풀이

f(4)에 대해 구한다고 할 경우 아래와 같이 구할 수 있다.
1. 1로 시작하는 숫자는 1xxx가 된다. xxx는 f(4)일 때의 가짓수가 동일하다.
2. 00으로 시작하는 숫자는 00xx가 된다. xx는 f(3) 일 때의 가짓수와 동일하다.
3. f(5)의 가짓수는 1로 시작하는 숫자와 00으로 시작하는 숫자의 가짓수를 합한 것과 동일하다.
 - f(5) = f(4) + f(3)
즉, 이 문제는 점화식이 1, 2인 피보나치 수열이다. 함수 구현은 피보나치 수열을 구현하듯이 하면 된다.

다만 결과 출력이 15746으로 나눈 나머지이고, 나머지 연산의 법칙상 (a % m + b % m) % m은 성립이 되므로# 피보나치 수열을 구하는 과정에서 각 수를 15746으로 나눈 나머지로 계산하여야 올바른 값을 얻을 수 있다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_1904()
{
	int N;
	cin >> N;
	int f1 = 1;
	int f2 = 2;
	int f3;
	if (N <= 2)
	{
		f3 = N == 1 ? 1 : 2;
	}
	else
	{

		for (int i = 3; i <= N; i++)
		{
			f3 = (f2 + f1) % 15746;
			f1 = f2 % 15746;
			f2 = f3;
		}
	}
	cout << f3 << endl;
	return;
}