11727번 2xn 타일링 2 with C++

문제

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

11727번: 2×n 타일링 2

 

해결한 방법

11726번 풀이에서는 2칸짜리 블럭과 1칸짜리 블럭으로 분할을 해서 각 케이스의 경우의 수를 합하는 것으로 정답을 구했습니다.
이 문제에서는 2칸짜리 서로 다른 블럭 두개와 1칸짜리 블럭으로 분할해서 풀면 됩니다.
따라서 11726번에서 구한 각 케이스의 경우의 수에서 각 2칸짜리 블럭을 선택해주는 경우의 수만 곱해주고 매번 10007으로 나누어서 정답을 구해줍니다.

#include <iostream>
using namespace std;

int combination[1001][1001];

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

	int input;
	cin >> input;
	int i, j;
	for (i = 1; i <= input; i++) {
		combination[i][0] = 1;
		for (j = 1; j < i; j++) {
			combination[i][j] = (combination[i-1][j] + combination[i-1][j-1]) % 10007;
		}
		combination[i][j] = 1;
	}

	int two = input / 2;
	int one = input % 2;
	int result = 0;
	int adder;
	while (two >= 0) {
		adder = combination[two + one][two];
		for (i = 0; i < two; i++){
			adder *= 2;
			adder %= 10007;
		}
		result += adder;
		result %= 10007;
		two--;
		one += 2;
	}

	cout << result;
	return 0;
}