[BOJ] 1904 01타일

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

Note

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;
}

2019-04-01 00:42:57에 Tistory에서 작성되었습니다.