[백준 11726] 2×n 타일링 (JAVA)

백준 11726번 문제 - 2×n 타일링

11726번: 2×n 타일링

---

문제 분석

 

 

• n이 주어졌을 때, 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 출력해라
  • 이해를 돕기 위한 n에 따른 방법의 수
    n = 1 : 1
    n = 2 : 2
    n = 3 : 3
    n = 4 : 5

---

 

해결 키 포인트

 

• DP로 구현
• 1부터 N까지 1을 만드는데 걸리는 시간 DP로 풀기
  • 쉽게 알 수 있는 dp 값 : dp[1] = 1 | dp[2] = 2
    
  • 3부터 N까지 dp 구하기 반복 : dp[i] = dp[i-1] (처음을 1x2로 했을 경우의 수) + dp[i-2] (처음을 2x1 2개를 했을 경우의 수) 

---

코드

 

import java.io.*;

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

        int N = Integer.parseInt(br.readLine());

        int [] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= N; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }

        bw.write(dp[N] + "\n");

        bw.flush();
        bw.close();
    }
}