[DP] BOJ 11726 번 문제

문제분석

내용이 어렵지 않아서

추가적인 설명은 굳이 필요 없을 것 같아서 패스할게요~

 

저만 그럴 수도 있지만...

처음에 이 문제를 보고 생각한 게

 

배열의 행을 2로 잡고 해야 되나?

도형을 뭐로 표현하지? 

라고

생각했었는데

그럴 필요가 없더군요... 

 

DP 문제 점화식만 파악하면 되는 문제입니다.

 

우선 눈으로만 봐도 알 수 있는 경우의 수를 정의해봅시다! 

 

D[n] = 가로길이가 n 인 직사각형을 채우는 경우의 수

A = 가로길이가 2 인 직사각형

B = 가로길이가 1 인 직사각형

이라고 했을 때,

 

D[0] = 0 

D[1] = 1

D[2] = 2

 

3가지 경우는 확실해집니다.

 

이제 D[3] 에 대해서 봅시다.

상황을 두 가지로 나누어 볼 수 있습니다.

 

D[3] 의 처음 블록을 A 로 시작하는 경우

이 경우 조금만 생각해보시면 알 수 있는 부분인데,

A 블록은 무조건 두 개씩 사용할 수밖에 없습니다.

그러면 가로길이가 1 밖에 안 남겠죠? 

이건 D[1] 의 경우의 수와 같습니다!

 

그리고 D[3] 의 처음 블록을 B 로 시작하는 경우

2 X 2 의 직사각형 블록이 남습니다.

이건 D[2] 의 경우의 수와 같네요?

 

따라서,

D[N] = D[N -1] + D[N -2]

라는 점화식이 도출될 수 있습니다.

 

 

 

 

코드

#include "bits/stdc++.h"

using namespace std;
int d[10005];
int n;
int mod = 10007;
int main()
{
	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] + d[i - 2]) % mod;
	}
	cout << d[n];


}