[백준][11726] 2xn 타일링



[11726] 2xn 타일링

문제


2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

bj_11726


입력


첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)


출력


첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.


입력 1

2

출력 1

2

입력 2

9

출력 2

55

1. 문제 설명


bj_11726

  • 처음봤을땐 이게 뭔가 싶은 문제이다. 하지만 굉장히 단순한 점화식으로 구현가능하다.

  • 위 사진을 보면 n=1, n=2를 기본값으로 두고 n=3 일 때 부터 규칙성이 보일것이다.
    n의 모양은 자세히 살펴보면 n-1의 모양에서는 세로 막대기 1개가 추가되고, n-2의 모양에서 가로 막대기 2개가추가된 모습이다.
    ++(주황색으로 표시한 모양은 n-2, 빨간색으로 표시한 모양은 n-1이다.)++

  • 점화식 : dp[i] = dp[i - 1] + dp[i - 2]
    문제에서 10007로 나눈 나머지를 구하라고 하였으니, 점화식 뒤에 % 10007를 적어주면 끝.


2. 소스 코드


#include <iostream>
#include <vector>

using namespace std;

int main() {
	const int MOD = 10007;
    
	int n;
	cin >> n;
    
	vector<int> dp(n + 2, 0);

	dp[1] = 1;
	dp[2] = 2;

	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
	}

	cout << dp[n] << endl;

	return 0;
}




© 2019. by mintheon

Powered by mintheon