[C/C++] 2xn 타일링 (백준 11726)

문제

 

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

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

 

 

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

 

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

 

입력

 

2

 

출력

 

2

 

입력

 

9

 

출력

 

55

풀이

 

이 문제는 저번에 풀다가 포기한 문제 중 한 문제라서... 일단 풀어보았습니다. 당시에는 기하학인가? 싶어서 조금 겁을 먹었었는데 자세히 보니 그냥 수학 문제라는 느낌이 들어서 자신감이 생겼습니다.

 

n의 크기에 따라 들어갈 수 있는 도형의 수가 정해집니다.

 

그림을 한 번 그려 보았습니다.

 

1은 1, 2는 2, 3은 3, 4는 5, 5는 8

1 2 3 5 8 ...

 

그렇습니다. 피보나치 수열을 따르는 겁니다. 잘하시는 분들 그리고 경험이 많은 분들은 9 55에서 눈치를 챈 사람도 있겠지만 저는 아직 노가다를 필요로하기 때문에 한 번 그려 보았습니다.

 

그럼 이제 피보나치 수열을 통해서 문제를 계산하면 끝입니다.

 

그런데... 평소에 사용하던 재귀를 통해서 구현을 하니 시간 초과가 났습니다. 그리고 이전에 사용했던 초반 부분의 정보를 통해서 배열에 저장해서 간단하게 메모이제이션을 했었는데도 시간 초과가 났습니다.

 

그래서 그냥 직접 구현 하기로 했습니다. 그럼 적어도 n만큼 반복문을 반복할테니 어떻게든 되겠지라는 생각으로 그냥 반복문으로 짰습니다. 시간 초과가 나는 분들이 계시다면 그냥 일반 반복문을 사용해보는 것도 좋을 것 같습니다.

코드

 

#include <iostream>

int main(void) {

	long long n;
	scanf("%lld", &n);

	long long result = 2;
	long long before = 1;

	if (n == 1) {
		printf("%d", 1);
	}
	else if(n == 2) {
		printf("%d", 2);
	}
	else {
		for (int i = 2; i < n; i++) {
			long long temp = (result + before) % 10007;
			before = result;
			result = temp;
		}
		printf("%lld", result%10007);
	}
	
	return 0;
}

 

설마하니 long long도 안먹힐 줄은 몰랐네요... 그래서 반복문으로 그냥 해버렸씁니다...