[백준 11726, Java] 2 Xn 타일링

문제

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

접근

1.처음 접근 방법 (1 X 2 타일의 갯수를 기준으로)

 - 1 X 2 타일을 0개 쓴다. 2개 쓴다, 4개 쓴다를 기준으로 잡았다. 예를 들어 N = 5라고 했을 때 1 X 2 타일을 0 개쓰면 2 X1 타일로만 채우게 되므로 경우의 수는 1이다.

 

 

1 X 2 타일을 1개를 쓴다고 했을 때, 1 X 2 타일 위 또는 아래에는 반드시 1 X 2 타일이 올 수 밖에 없으므로 1X2 타일은 짝수개를 쓰게 된다. 따라서 1 X 2 타일을 2개 쓰는 경우에는 

위의 경우를 쭉 나열해보니 1 X 2 타일의 갯수에 따라 1 X 2 타일의 위치가 될 수 있는 경우의 수를 구하면 될 거라고 생각했다. 0개이면 1가지, 1개 이면 4가지, 2개이면 몇가지 이렇게. 근데 이 방법의 경우 단순 조합으로 풀게 되면 1 X 2가 겹치게 되는 상황도 발생하게 되니 2X1타일의 갯수가 많아질 수록 경우의 수를 구하는 게 어려워지겠다는 생각을 했다.

 

2. 다 써보기

- 첫번째 방법으로만 생각하다가 막혀서 다 써봤다. 그랬더니 계단을 오르는 문제와 비슷해졌다. (계단을 오르는데 1계단 또는 2계단을 오를 수 있다. N개의 계단을 오르는 방법의 가지수는? ) 그래서 이 방법으로 풀었더니 맞았다. 

 

3. 점화식

- 2번을 점화식으로 나타내면 다음과 같다. F(N) 을 2*N 의 직사각형을 2 X 1 또는 1 X2 타일로 채우는 방법의 수라고 하면 F(N) = F(N-1)  + F(N-2)가 (2 X N-1 직사각형을 채우는 방법의 수 + 2 X N-2 직사각형을 채우는 방법의 수)  된다. 

 

check

- 출력을 보면 10007로 나눈 나머지를 출력하게 되어있다. 입력이 1,000이라고 하면 중간에 int범위를 넘어서게 되는 수가 있게 되므로 F(N)을 구할 때 %10007로 나눈 나머지를 배열에 넣어야 시간초과나 틀렸습니다가 뜨지 않는다.

 

comment

- 출력잘보기!

- 점화식으로 문제를 접근하는 거. 문제의 크기! 

 

 

소스코드

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static int[] tileCount;
    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine().trim());
        tileCount = new int[N+1];
        tileCount[0] =1;
        tileCount[1] = 1;

        makeTileBottomUp(N);
        bw.write(String.valueOf(tileCount[N]));
        bw.flush();
        br.close();
        bw.close();


    }
    public static void makeTileBottomUp(int N){
        for(int n = 2; n<=N ; n++ ){
            tileCount[n] = (tileCount[n-1] + tileCount[n-2]) %10007;
        }
    }
}