백준 11726번 2 * n 타일링

1. 문제 설명

문제 링크

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

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

• 입력
  • 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
• 출력
  • 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

2. 코드

import java.util.Scanner;

class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] dp = new int[n + 2];

       

        dp[1] = 1;

        dp[2] = 2;

        for (int i = 3; i <= n; i++) {

            dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;

        }

        System.out.println(dp[n] % 10007);

    }

}

3. 회고

Q. 문제를 보고 든 생각

• DP를 이용한 점화식 찾기
  
  • 해당 문제를 요구 하는 2 * N 의 타일을 그림을 그려 가며 경우의 수를 체크하였다.
  • 2 * 1 의 타일을 채 울수 있는 경우의 수는 1가지 이다.
  • 2 * 2 의 타일을 채 울수 있는 경우의 수는 2가지 이다.
  • 2 * 3 의 타일 또한 3가지 경우의 수가 나온다.
  • 이 문제의 점화식은 dp[i] = (dp[i - 1] + dp[i - 2]) %10007 이다.

4. 고쳐야 할점

자바가 익숙하지 않아서 더 많은 문제로 지속적으로 코드를 작성해야 점이 있다.