[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 11727

2*n짜리 직사각형을 1*2, 2*1, 2*2 짜리로 채우는 방법의 갯수를 구하기

 

가장 끝에 1*2, 2*1를 두는 각각의 방법을 d[n-2], d[n-1] 라고 한다.

이때, 끝이 1*2를 두개 두는 것은 2*2를 하나 두는 것과 같다.

즉, d[n-2]에 대해 2가지 경우가 있는 것이므로 d[n]=d[n-2]*2 + d[n-1] 이다.

 

n=1일 때 1(2*1짜리 하나)로 재귀를 빠져나온다.

n=2일 때 3(1*2짜리 두 개, 2*2짜리 하나)로 재귀를 빠져나온다.

 

import java.util.Scanner;

public class BOJ11727 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int x=sc.nextInt();
        int[] d=new int[x+1];
        System.out.println(operate(x, d));
    }

    static int operate(int x, int[] d){
        if(x==1) return 1;
        if(x==2) return 3;
        if(d[x]>0) return d[x];

        d[x]=operate(x-1,d)+operate(x-2,d)*2;
        d[x]%=10007;
        return d[x];
    }
}