[백준] 11726 2xn 타일링 자바(Java)

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

11726번: 2×n 타일링

문제를 풀어보고 오면 좋겠습니다.

 

문제는 2*n 크기의 직사각형을 2 * 1 타일로 채우는 방법의 수를 구하는 문제이다.

 

위 그림과 같이 직사각형을 채워나갈 수 있게 된다.

n의 값이 3, 4일 때부터 규칙이 보이기 시작한다.

 

n = 3 일 때

두 개의 박스로 크게 묶어두었다.

 

묶은 이유는

왼쪽 박스는 n = 2 일 때 타일을 채우는 방법에 2 * 1 세로 타일을 추가했고, 오른쪽 박스는 n = 1 일 때 직사각형을 채우는 방법에 1 * 2 가로 2개의 타일을 채웠다. ( 2 * 1 타일은 이미 왼쪽박스에서 다 넣었기 때문에, 1 * 2 직사각형 2개의 타일을 묶음으로 생각하면 편하다. )

 

n = 4 일 때

마찬가지로 두 개의 박스로 크게 묶어두었다.

n = 3 일 때 채우는 방법에 2 * 1 세로 타일 1개 추가 + n = 3 일 때 채우는 방법에 1 * 2 가로 타일 2개 추가

 

2 * n 크기의 직사각형을 2*1 타일로 채우는 방법의 수를 countTile( n )이라고 할 때 규칙성을 통해 아래와 같은 식이 나오게 된다.

countTile( n ) = countTile( n - 1) + countTile( n - 2) 

 

 

자바 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int input = Integer.parseInt(bf.readLine());

        /*
        규칙성 : dp[n] = dp[n-1] + dp[n-2];
        dp[1] = 1
        dp[2] = 2
        */

        int[] dp = new int[input + 1];

        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= input; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] ) % 10007;
        }

        System.out.println(dp[input]);
    }
}

 

이 문제는 11727 문제와 연결된다.

규칙을 이해하지 못하면 다음 문제를 풀 수 없게 된다.

11727 풀이 : https://iyk2h.tistory.com/307

Java - [백준] 11727 2xn 타일링 2