[백준 / DP] 11726 : 2 x n 타일링 (Java)

<정답>

import java.io.*;

class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[1001]; //n+1 하면 런타임 에러남

        dp[1] = 1;
        dp[2] = 2;
        
        for(int i=3; i<n+1; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 10007;
        }
        
        System.out.print(dp[n]);
    }
}

첫번째 DP 문제 풀어봤다.

 

DP문제 푸는 방법은 아래와 같다.

 

1. 테이블 정의 -> dp[i] = 2×i 크기의 직사각형을 채우는 방법의 수

 

2. 점화식 찾기 -> n이 1,2,3,4..일 때 방법이 몇가지 나오는지 직접 해보고, 그 안에서 규칙 찾기

n=1 > 1

n=2 > 2

n=3 > 3

n=4 > 5

n=5 > 8

까지 찾았으면 대충 이전꺼 두개를 더하면 나온다는 것을 알 수 있다.

n=9일 때 55라는 힌트를 줬으므로 위의 추측대로 계산해보면,

n=6 > 5+8=13

n=7 > 8+13 = 21

n=8 > 13+21 = 34

n=9 > 21+34 = 55

가 되고, 추측이 맞다는 사실을 알 수 있다.

점화식 : dp[i] = dp[i-1] + dp[i-2]

 

3. 초기값 정하기

dp[1] = 1dp[2] = 2이전값 두개가 필요하므로 n=1,2는 미리 정해둔다.