알고리즘 문제

[C/C++ 백준 2133번] 타일 채우기 (Silver 2)

새파란 공대생 2020. 5. 6. 23:50

https://www.acmicpc.net/problem/2133

 

2133번: 타일 채우기

문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복��

www.acmicpc.net

쉬울 줄 알았는데, 고민을 엄청나게 하게 만드는 문제였다. 우선 N이 홀수일 경우는 반드시 한 칸이 남기 때문에 모두 채울 수 없다. N이 짝수일 때 고민을 해야하는데, 카운팅의 기준을 이렇게 세우기로 했다.

 

사이트에서 제공하는 힌트 그림

저 이미지를 잘 보면, 세로선을 긋는다고 가정할 때 잘라지는 부위와 막히는 부위가 있다. 저 타일은 3×2, 3×4, 3×2, 3×4로 잘리게 된다. 이런 세로선이 처음 생기는 곳에 따라 경우를 나눈다. 즉, 3×2로 처음 잘릴 경우, 3×4로 처음 잘릴 경우,,,,,이런식으로 나눈다.

 

ㅇ ㅇ            
ㅇ ㅇ ㅇ ㅇ        
ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ    
ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ

o끝날 때 자르는,, 이런식으로? 2개짜리 o를 만드는 경우의 수는 3가지 이지만, 4이상의 o에 대해서는 모두 2가지 이다. 말로 하려니 어려운데, 이대로 하면 아래와 같이 코드를 짤 수 있다.

   

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
int main(void){
    int N, tile[31]={0,0,3}, cnt;
    scanf("%d",&N);
    for(int i=3; i<=N; i++){
        if(i%2==1)
            tile[i]=0;
        else{
            cnt=0;
            int slice=2;
            while(i-slice>0){
                if(slice==2)
                    cnt += 3*tile[i-slice];
                else
                    cnt += 2*tile[i-slice];
                slice += 2;
            }
            cnt += 2;
            tile[i] += cnt;
        }
    }
    printf("%d",tile[N]);
}