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

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

 

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

d[n]=d[n-2]+d[n-1]이다.

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

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

 

import java.util.Scanner;

public class BOJ11726 {

    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 2;
        if(d[x]>0) return d[x];

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