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

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

 

문제 출처

www.acmicpc.net/problem/11726

11726번: 2×n 타일링

---

※ 풀이

 

동적프로그래밍(DP)의 대표유형격인 문제이다.

 

n 번째 경우의 점화식을 세워서 값을 저장해나가면서 풀어가면 되는데

이 경우 단순하게

 

a[1]=1

a[2]=2

...

a[n]=a[n-1]+a[n-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 2;
        } else if (arr[idx] != 0) {
            return arr[idx];
        } else {
            long a = dynamic(idx - 1);
            long b = dynamic(idx - 2);
            arr[idx - 1] = a;
            arr[idx - 2] = b;
            return arr[idx] = (a + b) % 10007;
        }
    }
}