[백준] 11727번 2×n 타일링 2 - Java

[백준] 11727번 2×n 타일링 2 - Java

 

문제 출처

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

---

※ 풀이

동적프로그래밍(DP)을 활용하여 푸는 대표적인 유형이다.

이 문제도 2xn 문제 1번 과 유사하지만 2x2 블럭이 추가되었다.

 

마찬가지로 n번째 점화식을 세우기 위해 블럭의 수를 추론해보면

a[1]=1

a[2]=3

...

a[n] = a[n-1] + 2* a[n-2]

 

형태로 n-2 일때 * 2를 해야 하는 식이 나온다.

(n-2일때 블럭이 n-1일때 들어가지 못하는 형태가 2개씩 있기 때문)

---

※ 소스코드

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

public class Main {

    static long[] arr = new long[1001];

    public static void main(String[] args) throws IOException {
        //input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        System.out.println(dynamic(N));
    }

    static long dynamic(int idx) {
        if (idx == 1) {
            return 1;
        } else if (idx == 2) {
            return 3;
        } else if (arr[idx] != 0) {
            return arr[idx];
        } else {
            long a = dynamic(idx - 1);
            long b = 2 * dynamic(idx - 2);
            arr[idx - 1] = a;
            arr[idx - 2] = b;
            return arr[idx] = (a + b) % 10007;
        }
    }
}

 

---