백준11727 - 2×n 타일링 2

pa324·2019년 7월 15일
0

문제

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

입력

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

출력

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

풀이

해당 문제는 Dynamic Programmin으로 해결할 수 있는 문제 입니다. 문제의 규칙을 이용해서 점화식을 도출 하도록 하겠습니다.

  1. n=1인경우 2 x 1인 타일을 채우는 경우의 수는 1개 (2x1타일 이용)

    2x1크기의 타일을 2x1타일 1개를 이용해서 채울 수 있습니다.

  1. n=2인경우 2 x 2인 타일을 채우는 경우의 수는 2개 (2x2타일 이용)
    2x2크기의 타일을 2x1타일 2개를 이용하는 방법, 2x2타일을 2개이용하는 방법으로 총 2가지 경우의 수가 나오게 됩니다.
  1. n=3인경우 2 x 3인 타일을 채우는 경우의 수는 3개
    2x3크기의 타일을 2x1타일 3개로 채우는 방법, 2x2타일 2개와 2x1타일 1개, 마지막을 2x1타일 1개와 2x2타일 2개로 채우는 방법으로 총 3가지 경우의 수가 있습니다.

  2. n=4인경우 2 x 4인 타일을 채우는 경우의 수는 5개
    아래 그림과 같은 경우의 수를 찾을 수 있습니다.

  1. 점화식
    2xi 타일을 채우는 경우는 i-1번째경우의 수 + i-2번째 경우의 수를 합하면 구할 수 있습니다.
dp[i] = ' 2 x i 타일을 채울 수 있는 경우의 수 ' =  dp[i-1] + dp[i-2]
  1. 코드
#include<stdio.h>
int dp[10001];
int main(){
	int i,n;
	scanf("%d",&n);
	dp[0] = dp[1] = 1;
	for(i = 2; i<= n; i++) {
		dp[i] = dp[i-1] + dp[i-2];
		dp[i] %= 10007;
	}
	printf("%d",dp[n]);
	return 0;
}
profile
안녕하세요

0개의 댓글