[백준] 11726: 2 * n 타일링 - Java (DP)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

해당 문제는 피보나치 수열 DP 문제와 비슷하다.

모든 DP 문제가 그렇듯 n = 1일 때, 2일 때, 3일 때 ... ... 를 구해보면 패턴이 보인다.

 

그리고 그 패턴에서 나는 다음과 같은 점화식을 세웠다.

dp[i] = dp[i - 2] + dp[i - 1] 

 

  풀이

 

package src.dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Tiling {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[1001];

        dp[1] = 1;
        dp[2] = 2;

        // 점화식
        for(int i = 3; i <= n; i++){
            dp[i] = (dp[i - 2] + dp[i - 1]) % 10007;
        }

        System.out.println(dp[n]);

    }
}