다이나믹프로그래밍- 2xn타일링(백준 11726번)

1. 다이나믹프로그래밍- 2xn타일링(백준 11726번)

---

---

2. 다이나믹프로그래밍을 이용한 풀이

---

package dynamicProgramming;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Baejun11726tiling {
    static int[] memo=new int[1001];
    static void initMemo(int[] memo) {
        for(int i=0;i<1001;i++) {
            memo[i]=-1;
        }
        memo[1]=1;
        memo[0]=1;
    }
    static int tiling(int n) {
        if( memo[n]!=-1 ) {
            return memo[n];
        }
        memo[n]=(tiling(n-1)+tiling(n-2))%10007;
        return memo[n];
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine().trim());
        initMemo(memo);
        System.out.println(tiling(n));
    }
 
}
 

다이나믹 프로그래밍으로 풀기 전에 이 문제의 점화식을 먼저 구해보면 간단히 n=2,n=3,n=4 만 비교해보면 n=2는 2가지 n=3일떄는 3가지 n=4 일때는 5가지라는 경우의 수가 나온다. 즉, 이 문제의 점화식은 2x4=2x3 + 2x2 라는 점화식이 나온다. ->memo[n]=( tiling(n-1)+tiling(n-2) )%10007 하지만 문제의 전제에서 값에 10007의 나머지 값을 구하므로 % 10007을 해준다.(마지막에 결과에만 하는 것이 아니라 모든 경우에 % 10007이 적용되어야 한다.) 여기서 n-2 라는 수가 있다는 것을 주목하면 2번째 전까지의 수의 배열을 확인한다. 즉, 0과 1 두가지의 수를 초기화 시켜놔야 한다. 그래야 tiling(2)를 호출할때 tiling(1)+tiling(0) 을 호출했을때 배열의 있는 값을 이용해 이후의 값을 구할 수 있다.