백준 11726번 - 2×n 타일링 (C/C++)

 

 

 

 

 

학교에서 배운 DP 문제가 그대로 나와있었는데 C++로 풀어보는건 처음이기도 하고..

이제 백준으로 제대로 DP에 접근해보려고 해서 가장 기본적인 문제를 가져왔다.

 

 

 

 

 

 

 

 

입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
 
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

지난 학기때 기억을 스멀스멀 해보니 해당 DP문제는 n=1, n=2 부터 차근차근 접근해나가면 된다.

만약 ( 2 * 82 ) 라는 직사각형의 타일을 채우는 방법의 수를 구하라고 하면 매우 복잡해보이지만, 왼쪽부터 타일을 채워나간다고 생각하고 생각해보자. 

 

 

D(n) = D(n-1) + D(n-2)

// 2*n 크기 직사각형에 타일을 채우는 전체 경우의 수
( 첫 타일이 가로인 경우의 수 ) + ( 첫 타일이 세로인 경우의 수 )
== D(n-1) + D(n-2)

 

다음과 같은 로직이 성립한다. 왜 '-1', '-2'를 빼야 할까?

 

그림으로 설명해보면 다음과 같다. 간단하다.

 

첫 타일을 가로로 놓는 경우 남은 공백은 (n-1) 만큼의 영역일 것이고, 첫 타일을 세로로 놓은 경우 남은 공백은 (n-2) 만큼의 영역일 것이기 때문이다. 이 과정을 연쇄적으로 반복하다보면 결국 D(1), D(2)의 지점과 연결된다고 볼 수 있다.

 

우리는 이러한 식을 점화식이라고 한다.

 

2*1 영역을 타일로 채우는 경우의 수는 1, 2*2 영역을 타일로 채우는 경우의 수가 2라는 점은 누구나 알 수 있다.

이 점을 이용해서 DP에 맞는 점화식 코드를 작성해주겠다.

 

 

 

 

---

 

 

 

 

#include <iostream>
#include <vector>
using namespace std;
 
void DP(vector<int> & vec, int n)
{
	vec[0] = 1;
	vec[1] = 2;
 
	for (int i = 2; i < n; i++)
	{
		vec[i] = (vec[i - 1] + vec[i - 2]) % 10007;
 
	}
}
 
int main() {
	int n;
	cin >> n;
	vector<int> vec(n);
 
	DP(vec, n);
 
	cout << vec[n-1] << endl;
}

 

vector을 통해 핵심 점화식을 적어주고, 이를 독립된 함수로 빼주었다.

 

이제 이 저장된 vector 원소들 중 마지막 원소를 출력해주면?

우리가 구하고자 하는 2*n에 배치될 수 있는 타일의 경우의 수가 출력된다.