11726번: 2×n 타일링

문제:

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

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

입력:

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

풀이:

• 이 문제는 바텀업 방식과 탑다운 방식으로 모두 풀 수 있다. 아래 코드를 보면 두 경우 모두 적혀있다.
• 탑다운 방식과 바텀업 방식 모두 똑같은 개념을 사용한다. 우선, 사각형이 생길 수 있는 경우가 두가지가 있다. 세로는 2로 고정이고 가로로 1인 경우와 2인 경우가 있다. 가로의 길이가 1인 경우에는 경우의 수가 2x1 1개 밖에 없다. 가로의 길이가 2인 경우에는 경우의 수가 2x1 2개 / 1x2 2개로 나뉜다. 가로의 길이가 3인 경우에는 가로의 길이가 2인 경우 + 1인 경우이기 때문에 3인 경우부터는 분할정복 방식으로 문제를 풀면 된다.
• 탑다운 방식:
  • 탑 다운 방식으로 풀 경우 base case 즉 제일 아래로 갔을 때의 경우를 고려해주어야 된다. 이때 base case는 n이 1 혹은 2일 때 경우의 수 1과 2를 반환하는 것이다. 또한, 중복 계산을 방지하기 위해 해당 n값이 배열에 저장 된 값이 있을 경우 반환 해준다. 이제 막대기의 오른쪽 끝이 1일 때와 2일 때를 고려하여 문제를 푼다. 오른쪽 끝이 1일 때는 경우의 수가 1개이고 2일 때는 2개이지만 세로 막대기가 2개일 때 1일 때 경우의 수와 겹치기 때문에 가로로 된 막대기를 쌓는 경우의 수 1개만 고려해준다. 그러면 남은 막대기는 n-1과 n-2가 된다. 이런 식으로 계속 쪼개면 n이 1 혹은 2인 base case까지 내려간다. 마지막으로 이러한 값들을 배열에 저장하는 재귀함수로 구현하면 된다.
• 바텀업 방식:
  • 바텀업 방식은 조금 더 직관적이다. 탑다운 방식처럼 base case일 때를 배열에 먼저 저장하고 시작한다. 길이가 n인 막대기의 경우의 수는 길이가 n-1인 경우와 n-2인 경우를 더하면 나온다. 그러면 세로로 된 직사각형(2x1)이 3개인 경우 가로로 된 직사각형(1x2)이 2개 쌓아져 있고 옆에 세로로 된 직사각형이 좌우로 들어가는 경우의 수 2개가 있을 것이다. 하지만 세로로 된 직사각형이 좌우로 들어가는 경우는 이미 세로로 된 직사각형이 1개인 경우와 겹치기 때문에 사실상 가로로 된 직사각형 두개를 쌓는 경우의 수 밖에 없다고 생각하면 된다. 따라서 바텀업 방식은 이러한 방식을 하나씩 세면서 n까지 막대기를 만든다고 생각하면 된다. 결론적으로는 for문을 3부터 n까지 돌리며 n-1이였을 때의 조합 개수와 n-2일때의 개수를 더해주면서 배열에 저장해준다.
• 문제에서 10007의 나머지를 구하라고 하였으니 나머지 연산을 해준 뒤 배열에 저장 해 두어야 된다. 나머지 연산을 저장안하면 값이 너무 커져 배열에서 overflow가 발생하기 때문에 문제에서 나머지 연산한 값을 출력하라고 한 것 같다.

코드:

#include <iostream>

using namespace std;

int d[1001]; //바텀업인경우 = {0,1,2}

//탑다운 방식의 재귀 함수
int dp(int n){
	if(n==1) return 1; //1칸인 경우 경우의 수 1개
	if(n==2) return 2; //2칸인 경우 경우의 수 2개
	if(d[n]) return d[n]; //이미 값이 존재할 경우 배열에서 찾아옴
	return d[n] = (dp(n-1)+dp(n-2))%10007; //한칸인 경우와 두칸인 경우로 나눠 경우의 수 확인

}

int main(void){
	int n;
	//입력
	cin >> n;

	/* 바텀업 방식
	for(int i = 3; i<=n; i++){
		d[i] = (d[i-1]+d[i-2])%10007; //한칸인 경우와 두칸인 경우로 나눠 경우의 수 확인
	}
	cout<<d[n];
	*/

	//출력
	cout<<dp(n);
	
}