백준 1904번: 01타일

백준 온라인 저지(BOJ) 1904번 문제

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

1. 문제 요약

타일 두 종류가 있는데, 하나는 00, 하나는 1이다.

두 종류의 타일을 가지고 길이 N짜리 타일을 만들 수 있는 경우의 수를 구하시오.

2. 알고리즘

기본적인 다이나믹 프로그래밍 문제.

피보나치 수열이 나온다.

3. 코드

#include <iostream>
using namespace std;

int main() {
	int N;
	cin >> N;
	
	int a = 0, b = 1, c;
	for (int i = 0; i < N; ++i) {
		c = (a + b) % 15746;
		a = b;
		b = c;
	}
	cout << c << endl;
	
	return 0;
}