[백준 java] 11727 - 2xn 타일링 2

11727번: 2×n 타일링 2

---

내가 푼 방법은 n = 1부터 5까지 구하고 해당 결과로 점화식을 찾았다.

n = 1 : 1개

n = 2 : 3개

n = 3 : 5개

n = 4 : 11개 

n = 4일때 사각형을 채울 수 있는 경우의 수

따라서 dp[n] = dp[n-1] + dp[n-2]*2 이란 점화식이 나온다.

내가 푼 해결방식은 너무 별로라서 다른 풀이를 찾아봤는데

다음과 같이 n=3일때 사각형 배치 방식은

시작이 n=2 으로 시작하거나 

n=1 에 2x1사각형 가로로 두 개 or 2x2사각형 하나가 붙어있는 형태 즉 n=1로 두가지 형태를 만들 수 있게 된다.

따라서 점화식이 dp[n] = dp[n-1] + dp[n-2]*2 이 된다고 한다.

 

 

주의할점

여기서 끝내면 n이 약 40만 넘어도 int범위를 넘어서고 90만 넘어도 long범위를 넘어선다

10007로 나눈 나머지를 출력하는 것을 잊지말자.

---

import java.util.Scanner;

public class B11727 {
    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] = 3;
        for (int i = 3; i <= N; i++) {
          //  dp[i] = (dp[i - 1] + (dp[i - 2] * 2)) % 10007;
            dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
        }
        System.out.println(dp[N]);
    }
}