Baekjoon 1904 01타일

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

소스결과 5892 KB / 8 ms

출처 Baekjoon

언어 C++ 17

분류 다이나믹 프로그래밍

 

설명

00 또는 1 로만 구성된 길이가 N인 2진 수열의 개수를 구하자

 

N이 5일 때 까지의 결과값들은 1, 2, 3, 5, 8 이다.

피보나치 수열이다.

 

알고리즘

1. n을 입력 받는다.

2. 1 ~ 100만까지의 피보나치 수열을 구한다. 각각의 값은 15746으로 나눈 나머지로 구한다.

3. n번째에 있는 값을 출력해준다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 1000000;
const int DIV = 15746;

int dp[MAX] = { 1, 2, };

int main()
{
	for (int i = 2; i < MAX; i++)
		dp[i] = (dp[i - 1] + dp[i - 2]) % DIV;

	int n;

	cin >> n;

	cout << dp[n-1];

	return 0;
}