백준 11726 : 2×n 타일링(C언어, C++)

728x90

백준 문제

 

 

오늘은 백준 11726번 문제인 2×n 타일링을 풀어보겠습니다.

이러한 타일링 문제는 다이나믹 프로그래밍(DP)을 응용할 수 있는 좋은 기본 문제로 뽑히고 있습니다.

아래에서 문제를 한 번 확인해 봅시다.

 

 

문제 링크: 11726번: 2×n 타일링 (acmicpc.net)

11726번: 2×n 타일링

 

 

문제

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

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

 

입력

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

 

출력

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

 

 

 

해설

 

일단 이 문제를 해결하는 가장 간단한 방법은 각 n 마다 방법이 몇 개인지 확인해 보는 것입니다.

일단 n이 1일 때에는 아래 한 가지 방법만 가능합니다.

n=1 일때

 

 

n이 2일 때는?

아래와 같이 두 가지 방법이 가능합니다.

 

n=2

n=2

 

 

이제 n이 3인 경우를 확인해 봅시다.

n이 3인 경우 아래와 같이 세 가지 방법이 가능합니다.

 

n=3

n=3

n=3

 

 

아직까지는 감이 잡히지 않습니다.

한번더 볼까요?

n이 4인경우를 확인해 봅시다.

 

 

n=4

n=4

n=4

 

n=4

n=4

 

n이 4인경우 5가지가 있습니다.

제가 왜 노란 부분을 표시했을까요?

 

바로 n이 4인 경우를 만들기 위해선

n이 2인 경우에서 뒤에 n이 2인 경우를 추가해 주면 되며(2 × 2)

n이 3인 경우에서 뒤에 n이 1인 경우를 추가해주면 되기 때문입니다.(3 × 1)

이때 주의해야 할 점이 뒤에 n이 2인 경우를 추가할 때

 

이렇게 세로로 놓여있는 타일은 놓을 수 없다는 점입니다.

그 이유는 이렇게 놓게 되면 뒤에 n이 1인 경우를 추가할 때 중복되는 부분이 생기기 때문입니다.

 

1

2

 

위 두개는 모양이 똑같습니다.

그렇기에 뒤에 n인 경우 추가 시

아래와 같이 가로로 놓여있는 타일을 사용합니다.

이거 사용!

 

 

규칙을 말해보자면

f(n) = f(n-1) + f(n-2)입니다.

n인 경우를 구하기 위해서

n-1인 경우에서 뒤에 

n=1 일때

이 타일을 추가해 주면 되며

 

n-2인 경우에서 뒤에

n=2

이 타일을 추가해주면 됩니다.

 

 

 

코드

#include<stdio.h>
int main(void)
{
	long long a[1000];
	int n;
	scanf("%d",&n);
	a[0]=1,a[1]=2;
	for(int i=2; i<n; i++)
	{
		a[i]=a[i-1]+a[i-2];
		if(a[i]>10006)
			a[i]%=10007;
	}
	printf("%lld",a[n-1]%10007);
}

 

문제에서 정답을 10007로 나누라 하였습니다.

이는 정답이 매우 커지기 때문입니다.

그래서 계산을 수행할 때마다 10007로 나눈 나머지값을 저장해 줍시다.

이래도 정답에는 아무런 변화가 없습니다.

 

정답!

 

이상 백준 11726번 2×n 타일링 문제를 풀어보았습니다.

다이나믹 프로그래밍을 연습하기 위한 좋은 문제이니 꼭 풀어보시기 바랍니다.

그리고 이 문제는 타일링 문제 중 가장 기본 문제이니 심화 문제도 풀어보도록 합시다.