[C++]백준 11726번: 2xn 타일링

문제

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

문제이해

 

• 첫째 줄에 n을 입력합니다.
• 정답이 되는 방법의 수를 10007로 나눈 나머지를 출력합니다.

이 문제는 다이나믹 프로그래밍을 사용해야합니다. 방법의 수를 찾기 위해서는 우선 점화식부터 찾아야합니다.

 

이를 배열로써 설명해보겠습니다. dp[i]는 2xi 크기의 직사각형을 채우는 방법의 수를 의미합니다.

dp[1]은 1, dp[2]는 2, dp[3]은 3이라고 할 수 있습니다.

그렇다면 dp[4]의 값은 얼마일까요 dp[2]의 상태에서 가로블럭 2개짜리를 오른쪽에 놓으면 dp[4]가 될 수 있습니다. dp[3]의 상태에서 세로블럭 1개짜리를 오른쪽에 놓으면 dp[4]가 될 수 있습니다. 따라서 dp[4]는 dp[3]의 값과 dp[2]의 값을 더하면 나옵니다.

 

이를 통해 점화식이 dp[i+2] = dp[i+1] + dp[i]라는 것을 확인했습니다. 2xn 크기의 직사각형을 채우는 방법의 수를 알기 위해서는 dp[n]의 값을 확인하기만 하면 됩니다.

 

이 문제에서는 dp[n]의 값을 10007로 나누어서 출력해야 합니다. 점화식을 통해 저장될 dp[n]의 값들을 10007로 나눈 나머지로 저장하기만 해도 모든 값들이 dp[n]을 10007로 나눈 나머지로 저장되게 될겁니다.

 

다음은 위의 내용을 토대로 만든 코드입니다.

 

문제풀이

#include <iostream>
#include <vector>
using namespace std;

vector<long long> dp(1001);

void method() {
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
	for (int i{ 4 }; i < dp.size(); i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
		dp[i] %= 10007;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	method();
	int N;
	cin >> N;
	cout << dp[N];
}

 

문제후기

점화식을 찾는건 쉬웠으나 10007로 나눈다는 것에서 헷갈렸던 문제였습니다.