[백준 11726] 2*n 타일링 - JAVA [DP]

안녕하세요 놀이방사장입니다.

 

이번 포스팅은 백준 11726

"2*n 타일링" 입니다.

 

이번 문제도 DP문제입니다.

11726번: 2×n 타일링

일단 DP이기 떄문에 값을 저장해줄 배열을 선언합니다.

n의 크기가 최대 1000이기 떄문에 

static int[] dp = new int[1001];

위와 같이 배열을 선언해줍니다.

 

이제 점화식을 찾아야합니다

혹시 한 번 그려보면

n = 1 -> 1개

n = 2 -> 2개

n = 3 -> 3개

n = 4 -> 5개

이렇게 정답이 나옵니다.

여기서 찾을 수 있는 점화식은 ?? -> dp[n] = dp[n-1] + dp[n-2];

가 나오게 됩니다.

 

이걸 코드로 구현해보겠습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main{
    static int[] dp = new int[1001];
    public static int getTiling(int x){
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3;i<=x;i++){
            dp[i] = (dp[i-1] + dp[i-2])%10007;
        }
        return dp[x];
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = getTiling(Integer.parseInt(br.readLine()));
        sb.append(n);
        System.out.println(sb);
    }
}

그리고 마지막에 10007로 나눈 수를 출력한다 라고 문제에 나와있기 떄문에 dp값을 계산 할 때 %10007을 해줍니다!