BOJ 백준 11726 2xN 타일링

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

11726번: 2×n 타일링

문제 풀이 )

위의 사진을 볼 때 타일의 끝이 채워지는 방식은 위와 같이 두 가지 경우가 존재한다.

 

    1. 길이가 1이 남고 1x2 타일로 채워진 경우

 

    2. 길이가 2가 남고 2x1 타일 2개로 채워진 경우

 

타일의 끝에 길이가 3이 남는 경우는?

n = 3 타일

n이 3인 타일이 채워지는 방식은 위와 같이 3가지 경우가 존재한다.

 

채워지는 방식 중, 

 

    첫 번째는길이가 1 남고 1x2 타일로 채워지는 경우 에 해당한다.

 

    두 번째는 길이가 2가 남고 2x1 타일 2개로 채워진 경우 에 해당한다.

 

    세 번째는 1x2 타일 한 개와 2x1 타일 2개로 끝나는 것이 아니라, 

        길이가 1 남고 1x2 타일로 채워지는 경우 에 해당한다.

 

따라서 모든 타일의 끝은 위에서 말했던,

 

    1. 길이가 1이 남고 1x2 타일로 채워진 경우               => n - 1개의 타일을 채우는 방법의 수

 

    2. 길이가 2가 남고 2x1 타일 2개로 채워진 경우          => n - 2개의 타일을 채우는 방법의 수

 

이렇게 두 가지 방식으로만 끝난다. 따라서,

n개의 타일을 채우는 방식은 n-1개의 타일을 채우는 방법의 수와 n - 2개의 타일을 채우는 방법의 수의 합이 된다.

 

=> dp[n] = dp[n - 1] + dp[n - 2]

 

소스 코드

#include <cstdio>
#define MOD 10007

using namespace std;

const int SIZE = 1010;
int n;
int dp[SIZE] = { 0 };
int main()
{
	scanf("%d", &n);
	dp[0] = 1;
	dp[1] = 2;

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

	printf("%d\n", dp[n - 1]);
	return 0;
}

11727 2xN 타일링 2

https://onecoke.tistory.com/entry/BOJ-%EB%B0%B1%EC%A4%80-11727-2xN-%ED%83%80%EC%9D%BC%EB%A7%81-2