백준 1904 01타일

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

 

풀이

n=1 1	n=2 00 11	n=3 100 111 001	n=4 0000 0011 1100 1111 1001	n=5 00100 00111 00001 10000 10011 11100 11111 11001
개수 : 1	개수 : 2	개수 : 3	개수 : 5	개수 : 8

 

n이 3일때는 n이 1일때의 1에 00을 앞에 붙인 001, n이 2일때의 00, 11에 앞에 1을 붙인 100, 111 총 3개가 올 수 있다.

앞에 01, 10, 0은 못붙인다.

이를 확장하면 n = n-1 + n-2의 점화식이 나온다.

dp의 bottom-up으로 구현한다.

 

---

구현

%15746을 해주지 않으면 약 n이 90에서 long long 자료형을 초과한다. 

//c++

#include <iostream>

using namespace std;

long long dp[1000001];

int main() {
	int n;
	cin >> n;
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2])%15746;
	}
	cout << dp[n];
}