[백준 1904] 01타일 (C++)

문제 링크: www.acmicpc.net/problem/1904

1904번: 01타일

 

1. 주의할 점

- DP를 사용해서 문제를 해결한다(점화식)

 

2. 구현

- 1개의 타일: 1개(1)

- 2개의 타일: 2개(00, 11)

- N개의 타일을 사용할 때

: (N-1개의 타일 + N-2개의 타일)%MOD (여기서 MOD는 15746)

따라서 점화식은 N>=3일때, Arr[N] = (Arr[N-1] + Arr[N-2])%MOD로 이루어진다

#define MOD 15746
#include <iostream>
using namespace std;
int arr[1000001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num;
	cin >> num;
	arr[1] = 1;
	arr[2] = 2;
	for (int i = 3; i <= num; i++)
		arr[i] = (arr[i - 1] + arr[i - 2]) % MOD;
	cout << arr[num] % MOD;
	return 0;
}