DP알고리즘 문제 풀이 (백준 알고리즘 11726)

백준 알고리즘 11726번 2Xn 타일링

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.


설명

DP 알고리즘은 큰 문제를 해결 가능한 작은문제로 나누는 것으로 시작한다.
크기가 n인 직사각형의 방법의 수를 구하고 싶다면,
1. n-1의 크기의 직사각형의 수를 구한다음 새로모양의 직사각형을 붙이면 된다.

 
2. n-2의 크기의 직사각형의 수를 구한다음 가로모양의 직사각형 두개를 붙이면 된다.




여기서 주의할 점은 n-2의 크기일 때 새로모양의 직사각형 두개를 붙이면 안 된다. 왜냐하면 이 경우의 수는 이미 1번에서 체크했기 떄문이다.


요약

n크기의 직사각형의 경우의 수는 1번의 경우와 2번의 경우를 더한것이다.
즉 [n]= [n-1] + [n-2] 가 성립한다.


소스 코드

import java.util.*;
public class Main{
    static int[] dp;
 
 public static void main(String args[]){
  Scanner sc = new Scanner(System.in);
  int width;
        width = sc.nextInt();
        dp = new int[width+1];
        solve(width);
        System.out.print(dp[width]);
       
 }
    static int solve(int x){
        if(x==1){dp[x]=1;return dp[x];}
        if(x==0){dp[x]=1;return dp[x];}
        if(dp[x]!=0){return dp[x];}
        dp[x] = (solve(x-1) + solve(x-2))%10007;
        return dp[x];
       
        }
}