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

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

11727번: 2×n 타일링 2

---

문제 분석 

 

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

---

해결 포인트

•  

 

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

---

코드

 

import java.io.*;

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]*2) % 10007;
        }

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