다이나믹프로그래밍1 - 백준 1904번 01타일

www.acmicpc.net/problem/1904

1904번: 01타일

IDEA

규칙만 찾으면 된다. 써보자 

N = 1 1개  1 

N = 2 2개  00 , 11

N = 3 3개 100 , 001, 111

N = 4 5개 1100 , 1001 , 0011, 0000, 1111

dp[n] = dp[n-1] + dp[n-2] (n > 2) 라는 점화식을 세울 수 있다. 

그 후 문제의 조건에 맞게 15746으로 항상 나눠주면 된다. 

 

코드 

#include <iostream>
#include <vector>
using namespace std;
int dp[1000001] = {0};
int main() {
	int n;
	scanf("%d", &n);
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] % 15746 + dp[i - 2] % 15746) % 15746;
	}
	printf("%d", dp[n]);
}