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

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

1904번: 01타일

백준 1904번 01타일을 풀었습니다.

간단한 DP문제입니다. 피보나치 수열같이 규칙을 찾고 점화식을 만들면 됩니다.

 

아래는 전체 코드입니다.

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

#define MOD 15746
int N;
int arr[1000000];

int DP(int n) {
	if (arr[n] != 0)
		return arr[n];
	if (n == 0)
		return arr[n] = 1;
	if (n == 1)
		return arr[n] = 2;
	
	return arr[n] = DP(n - 1) % MOD + DP(n - 2) % MOD;
}

int main() {
	cin >> N;
	DP(N - 1);

	cout << arr[N - 1] % MOD;

	return 0;
}