1x2 모양의 타일과 2x1 모양의 타일로 2xn 크기의 직사각형을 채우는 방법의 수를 구하는 문제이다.
위와 같은 직사각형을 1x2, 2x1 두 개의 타일로 가득 채워야되는 것이다.
이 타일들을 이용해 저 직사각형을 채우는 경우의 수를 한 번 생각해보자. 쉽게 생각할 수 있는 방법 말고 예외적이고 뒤죽박죽으로 채우는 경우를 생각해보자. 해보면 알겠지만 이 문제에는 그런게 없다. 1x2 타일과 2x1 타일이 어지럽게 섞여있는 그런 조합은 존재하지 않는다.
가로로 누워있는 1x2 타일을 하나 집어넣는다고 생각해보자. 그럼 위 또는 아래에 공간이 비어 있을 것이다. 그곳을 2x1 타일로 채울 수 있을까? 불가능하다.
1x2 타일을 하나 썼으면 반드시 1x2 타일을 하나 더 써서 정사각형 형태로 채워줘야 하는 것이다. 즉, 이 문제는 사실 1x2 타일과 2x1 타일로 직사각형을 채우는 게 아니라 2x2 타일(1x2 타일 두개의 조합)과 2x1 타일로 채우는 경우의 수를 구하는 것이다.
이렇게 생각해보면 직사각형의 높이도 2이고, 타일들의 높이도 전부 2이다. 즉 어떤 타일을 사용하든 높이에는 전혀 신경 쓸 필요가 없다. 가로로 어떤 순서로 나열할지만 생각하면 된다. 그럼 이 문제를 또 다시 다르게 생각해볼 수 있다.
길이 n을 1과 2로 가득 채우는 경우의 수 즉, 숫자 n을 1과 2의 합으로 나타낼 수 있는 경우의 수를 구하는 문제인 것이다.
예를 들어, n=4이면
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
이렇게 5가지 방식으로 나타낼 수 있다.
n이 1 ~ 5인 경우를 직접 적어봤다. 여기서 우리는 규칙을 찾을 수 있다.
3을 만드는 방법들에 2를 더해주면 5를 만드는 방법이 되고
마찬가지로 4를 만드는 방법들에 1을 더해주면 5를 만드는 방법이 된다.
n이 주어졌을 때 경우의 수를 f(n)이라고 하면
f(n) = f(n-1) + f(n-2) 이 성립하는 것이다. 우리는 피보나치 수열을 출력하기만 하면 되는 것이다!
문제에서 10,007로 나눈 나머지로 출력하라고 했으니 이 부분만 주의하면 된다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
int n; scanf("%d", &n);
int arr[1001];
arr[1] = 1; arr[2] = 2;
for (int i = 3; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
arr[i] %= 10007;
}
printf("%d", arr[n]);
}
이런식으로 값을 저장하면 10007로 나눈 나머지가 제대로 저장되는 게 맞는지 의문이 들 수 있다. 결론부터 말하자면, 의도한대로 잘 저장된다. 아래는 이에 대한 설명이다.
우리가 지금 궁금한 것은
arr[i] % 10007 = {(arr[i-1] % 10007) + (arr[i-2] % 10007)} % 10007
이 식이 성립하는가이다.
이 식이 일반적으로 성립하는지 알아보기 위해 arr[i] = x, arr[i-1] = a, arr[i-2] = b 그리고 10007 = k로 표현하겠다.
우선 x = a+b이다. arr[i] = arr[i - 1] + arr[i - 2] 이므로.
그리고
a = pk + r
b = qk + s라고 하자.
그럼, 식을 이렇게 바꿀 수 있다.
(pk + r + qk + s) % k = {(pk + r) % k + (qk + s) % k} % k
우리는 (pk + r + qk + s) % k = (r+s) % k 라는 것을 알 수 있다.
또한, (pk + r) % k = r 이고, (qk + s) % k = s이다.
그럼 결과적으로 좌변과 우변은 모두 (r + s) % k 로 같은식이 된다.
댓글