[C/C++] 백준 1904번 - 01타일 (DP)

 

#include <iostream> 
using namespace std;

int DP[1000001];
int N;

int main() 
{
	cin >> N;

	DP[1] = 1;
	DP[2] = 2;

	for (int i = 3; i <= N; i++) 
	{
		DP[i] = (DP[i - 2] + DP[i - 1])%15746; // 요기서 나눠주지 않으면 long long의 범위를 넘어설수도 있음
	}

	cout << DP[N] << "\n";

	return 0;
}

 

 

DP[N]

=

DP[N-2]

+

DP[N-1]

1. [N-1] 자리 2진 수열에서 [N] 자리 2진 수열을 만들 수 있는 경우의 수는 마지막 칸에 1이 오는 것 이외에는 없다.

2. [N-2]자리 2진 수열에서 [N] 자리 2진 수열을 만들 수 있는 경우의 수는 마지막 2칸에 00이 오는 것 이외에는 없다.
(마지막 2칸에 11이 오는 경우는 [N-1]자리 2진 수열에서 [N] 자리 2진 수열을 만들 수 있는 경우의 수에 포함됨)

따라서 점화식을 만들어보면 A[n]=A[n-1]+A[n-2] 이다. 점화식에서 보이듯이 피보나치 수열이다. 그리고 수가 얼마나 커질지 예상을 못하고 마지막 DP[N]을 출력할 때 DP[N]%15746를 해줬었는데 문제의 뜻은 DP로 구할 때마다 %15746을 해줘야 했었다.(그렇지 않으면 long long의 범위를 넘어서서 제대로 된 값이 출력이 안됨!) 

 

간단한 DP문제였고 풀고나면 쉬운 문제다. 근데 매번 느끼는 거지만 처음에 문제 마주했을 때 어떻게 풀어야 할지 감이 안 오는데 아직 익숙지 않아서 그런가 보다.