11726 2xN 타일링 (동적계획법) [Silver III]

11726번: 2×n 타일링 (acmicpc.net)

 

동적 계획법

 

2 * N 크기의 직사각형을 1 * 2, 2 * 1 크기의 타일로 채우는 방법의 수를 구하는 문제입니다.

이런 문제는 항상 패턴을 분석하는 것을 먼저 해야 합니다.

 

풀이법

우선 예시를 그려보겠습니다.

⌈ ⌉
⌊ ⌋ , [ㅡㅡ]

N = 1
⌈ ⌉ 
⌊ ⌋  1개

N = 2
⌈ ⌉⌈ ⌉  [ㅡㅡ] 
⌊ ⌋⌊ ⌋, [ㅡㅡ]  2개

N = 3
⌈ ⌉⌈ ⌉⌈ ⌉  ⌈ ⌉ [ㅡㅡ]  [ㅡㅡ]⌈ ⌉
⌊ ⌋⌊ ⌋⌊ ⌋, ⌊ ⌋ [ㅡㅡ], [ㅡㅡ]⌊ ⌋  3개

N = 4
⌈ ⌉⌈ ⌉⌈ ⌉⌈ ⌉  ⌈ ⌉⌈ ⌉[ㅡㅡ]  ⌈ ⌉[ㅡㅡ]⌈ ⌉  [ㅡㅡ]⌈ ⌉⌈ ⌉  [ㅡㅡ][ㅡㅡ]
⌊ ⌋⌊ ⌋⌊ ⌋⌊ ⌋, ⌊ ⌋⌊ ⌋[ㅡㅡ], ⌊ ⌋[ㅡㅡ]⌊ ⌋, [ㅡㅡ]⌊ ⌋⌊ ⌋, [ㅡㅡ][ㅡㅡ]  5개

 

 

어떻게 채워야 할지는 감이 안오지만 개수에서 패턴이 하나 보이네요

N이 3일 때의 타일을 채우는 경우의 수 = N이 2일 때 경우의 수 + N이 1일 때 경우의 수

N이 4일 때의 타일을 채우는 경우의 수 = N이 3일 때 경우의 수 + N이 2일 때 경우의 수

 

즉

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

라는 조합식을 생각해 볼 수 있겠습니다.

 

 

정답 코드

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);

	cin >> N; 

	D.resize(N + 1); 
	D[1] = 1;
	D[2] = 2; 

	for (int i = 3; i <= N; i++) {
		D[i] = (D[i - 1] + D[i - 2]) % 10007;
	}
	 
	cout << D[N];  
}

 

 

톱-다운 방식으로 구현한다면 아래 처럼 할 수 있겠습니다.

long Function(int id)
{
	if (D[id] > 0)
		return D[id];	
	 
	return D[id] = (Function(id - 1) + Function(id - 2) ) % 10007; 
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);

	cin >> N;

	D.resize(N + 1); 
	D[1] = 1;
	D[2] = 2; 

	cout << Function(N);  
}