백준 11727번: 2xn 타일링 2

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

11727번: 2×n 타일링 2

 

 

 

 

문제

 

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

 

 

 

 

 

이 문제는 11726번 문제와 유사하다.

2020/01/14 - [백준 알고리즘] - 백준 11726번: 2xn 타일링

백준 11726번: 2xn 타일링

 

 

 

11726번 문제에서 n-2 크기의 직사각형에 2x2 타일을 추가하는 경우를 추가하면 된다.

 

 

 

코드

 

#include <stdio.h>

int dp[1000001];

int main(){
	int n;
	scanf("%d",&n);

	dp[0] = 1;
	dp[1] = 1;

    // 11726에서 
    // 1. 2*1 두 개 붙이는 경우
    // 2. 2*2 하나 붙이는 경우
    // 하나의 경우의 수가 추가됨
	for(int i = 2;i <= n;i++){
		dp[i] = (dp[i - 1] + 2 * dp[i-2]) % 10007;
	}

	printf("%d\n", dp[n]);
}