01타일(백준 1904번)

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

다이나믹 프로그래밍(동적계획법)을 연습할 수 있는 문제이다.
다이나믹 프로그래밍의 경우 점화식을 세울 수 있으면 쉽게 문제를 해결할 수 있다.

이 문제의 경우, 경우의수를 하나하나 나열해보면

dp[1] = 1		//1
dp[2] = 2		//00, 11
dp[3] = 3		//100, 001, 111
dp[4] = 5		//0011, 1001, 1100, 0000, 1111
dp[5] = 8		//11100, 11001, 10011, 00111, 00001, 00100, 10000

이 된다.

이것을 통해 점화식을 세워보면

dp[i] = dp[i-1] + dp[i-2]

가 된다.

이것을 코드에 적용시키면 된다.

#include <iostream>
using namespace std;

int dp[1000001] = { 0, };

int main() {

	int n;
	cin >> n;

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

	cout << dp[n];

}