[C++] 백준 1904번 01타일

다이나믹 프로그래밍 문제입니다.

 

피보나치 수열의 규칙을 하고 있어서

DP[i] = DP[i - 1] + DP[i - 2];

로 점화식을 세워서 문제를 풀었습니다.

 

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

int DP[1000010];

int main(int argc, char *argv[])
{
	int n;

	memset(DP, 0, sizeof(DP));

	DP[1] = 1;
	DP[2] = 2;

	cin >> n; 

	for (int i = 3; i <= n; ++i) {
		DP[i] = (DP[i - 1] + DP[i - 2]) % 15746;
	}

	cout << DP[n] << endl;

	return 0;
}