[백준/Java] 11726번 : 2xn 타일링

https://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로 나눈 나머지를 출력한다.

소스코드

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

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

문제풀이

dp를 내가 정확히 이해했는지는 모르겠지만 아마 dp에서 바텀업방식인 것 같다.
점화식을 잘 생각해보면 n이 홀수일 땐 이전 방식에서 세로로 긴 직사각형 하나만 붙이는거니까 이전과 동일하다고 볼 수 있다.
n이 짝수이면 이전에 홀수 방식에서 세로로 하나 더 붙인거랑 이를 가로 2개로 바꾼거로 2가지의 경우의 수가 있는데 이는 n-2의 개수에서 2배한것과 같다고 볼 수 있는데 이 때 n-1이 n-2와 같으므로 n = n-1 + n-2 로 표현할 수 있고 이는 n이 홀수일 때도 동일하게 적용된다.
피보나치 수열과 유사한 것 같기도..?
- BufferedReader사용해서 n 구해준다.
- 배열을 선언해서 도출한 점화식을 적용해서 n까지 타일을 배치하는 순서를 구해준다.