[BOJ] 1904번 : 01타일

1. problem : 

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

 

2. solution 1:

#include <bits/stdc++.h>
using namespace std;
const int mod = 15746; 
int n; 
int d[1000005]; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n; 
	d[1] = 1, d[2] = 2;
	for (int i = 3; i <= n; i++) d[i] = (d[i - 1] % mod + d[i - 2] % mod) % mod; 
	cout << d[n];
}

dp를 이용해 풀었다. 따라서, 세가지 스텝을 따른다. 

1. 테이블을 정의한다. d[i] = i자리를 만드는데 필요한 경우의 수

2. 점화식을 작성한다. d[i] = d[i-1] + d[i-2] 

3. 초기값을 설정한다. d[1] = 1, d[2] = 2