문제 링크 (알고스팟)
https://algospot.com/judge/problem/read/ASYMTILING


문제 이해

2 x n크기의 직사각형 공간을 2x1혹은 1x2 크기의 타일로 완전히 채우는 방법의 수를 구하는 문제이다.

타일의 배치가 좌우대칭인 것은 제외한다.


풀이

예를 하나 뽑아서 2 x 6 크기의 공간을 채우는 경우를 생각해 본다.

여기서 2 x 6 크기의 공간을 채우는 여러 경우들을 2가지로 나눌 수 있다.

A. 맨 마지막 타일이 세로로 되어 있음

B. 맨 마지막 타일이 가로로 2개 되어 있음


남은 부분의 크기를 보면,

A의 경우 나머지 공간의 너비는 5이고

B의 나머지 공간의 너비는 4이다.


즉, A에서 남은 부분을 채우는 방법의 수는, 이 문제에서 너비가 5인 공간을 채우는 경우의 답과 같다.

B의 나머지 부분을 채우는 방법의 수 역시 너비가 4인 공간을 채우는 경우의 답과 같다.

여기서 이 문제의 재귀적 속성을 발견할 수 있으며

이 문제를 Dynamic Programing (동적 계획법)으로 풀 수 있다는 것을 알 수 있다.


상향식(bottom-up)으로 어떻게 풀 지를 구체적으로 생각해 보면,

- n=1 일 때 (1 가지)

- n=2 일 때 (2 가지)
- n=3 일 때는  (n=2의 가지수) + (n=1의 가지수)

'n=2의 가지수'는 위 그림에서 A의 경우이고, 'n=1의 가지수'는 위 그림에서 B이다.


- n=4일 때는 (n=3)의 가지수 + (n=2의 가지수)

...

...

..


n = k일 때는 (n=k-1 의 가지수) + (n=k-2 의 가지수)


어디서 본 적이 있는 점화식이 나온다. 바로 피보나치 수열이다.




그런데 문제에서 좌우대칭인 경우는 제외하라는 조건이 있다.

이번에는 채워야 할 공간의 크기가 짝수인 것과 홀수인 것으로 나누어 생각해야 한다.


공간의 크기가 홀수일 때 좌우대칭이 되기 위한 조건은

가운데에 블록이 세로로 있어야 하며 분할된 한 쪽 너비는 (int)n/2이다.


공간의 크기가 짝수일 때는 분할된 한 쪽 너비가 n/2이다.




분할된 너비에 해당하는 경우의 수를 빼면 최종적인 답을 구할 수 있다.






구현

대칭인 경우를 제외시키기 위해 너비의 절반을 구해야 하는데,

피보나치 수열을 구하는 과정에서 같이 계산하도록 했다.


그리고 답을 리턴할 때, 이 문제에서 나머지연산한 결과를 요구하므로

계산 과정에서 그 수를 초과하지 않도록 주의하여야 한다.

A - B%mod + mod 와 같이 더해주면 값이 음수가 되는 것을 방지할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
 
using namespace std;
 
int main(void)
{
    int mod = 1000000007;
 
    int count;
    int input;
 
    int fibo2;
    int fibo1;
    int fibo;
 
    cin >> count;
 
    while (count--) {
        fibo2 = 0;
        fibo1 = 1;
        fibo = 0;
 
        cin >> input;
        if (input <= 2) {
            cout << 0 << endl;
            continue;
        }
 
        int p1=0, p2=0;
 
        for (int i = 1; i <= input; i++) {
            fibo = (fibo1 + fibo2) % mod;
            if (i == input / 2) {
                p1 = fibo1;
                p2 = fibo;
            }
 
            fibo2 = fibo1 % mod;
            fibo1 = fibo % mod;
 
        }
       
        if (input & 1) {  //input is odd
            p1 = 0;
        }
        cout << (fibo - (p1 + p2)%mod + mod)%mod <<endl;
    }
    //end while
    
    return 0;
}
cs








+ Recent posts