[BOJ] 11726 - 2×n 타일링 JAVA

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

 

 

 

 

 

풀이 .

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
        }
        System.out.println(dp[n]);
    }
}

 

n번째 칸을 채울 수 있는 경우는 두가지가 있다.

1. n-1번째까지 모두 채운 후 n번째에 세로블럭 하나를 놓는다.

2. n-2번째까지 모두 채운 후 n-1, n번째에 가로블럭 둘을 놓는다.

 

dp[n] = "n번째까지 타일을 채울 수 있는 모든 경우의 수" 라고 한다면

dp[n] = dp[n-1] + dp[n-2] 로 해결이 가능하다.

 

접근은 잘 했는데 초기화 문제 때문에 ArrayIndexOutOfBounds 런타임 에러로 애를 먹었다.

 

dp[0] = 0;

dp[1] = 1;

dp[2] = 2

로 초기화를 하고 i = 3부터 반복을 돌렸는데, 이렇게 하면 n = 1 일 때, dp[2] 에서 배열 범위 문제가 발생한다.

 

초기화 부분을 수정하여 정답처리 되었다.

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

n-2에서 세로블럭을 두 개 놓아서 채우는 경우를 고려하지 않는 이유?

-> 이건 이미 n-1에서 세로블럭 놓는 경우에 포함되어있음 (연속된 세로블럭을 놓는 것이므로)