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

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

DP 문제를 다루는 글에서 항상 언급하지만, 먼저 노가다로 n = 1, 2, 3, 4, 5 정도 까지 그려보거나 계산하고 거기서 점화식을 추출하는 방식으로 한다. 

 

특히 이렇게 점화식을 가져올 수 있는 문제에서는 말이다. 여기서는 어떤 점화식이 있을까?

 

그래서 그려보았다.

 

 

n = 4 까지만 그려보았다. 그림에는 없지만 n = 5 일 때는 21 개 이다.

 

나는 이 챕터에서 내가 점화식을 추출하게 된 과정을 써보려 한다.

 

 

n = 1: 1

n = 2: 3

n = 3: 5

n = 4: 11

n = 5: 21

 

이제 n = 5 일 때를 가정하여 어떻게 하면 21이 나올 수 있을까 생각해 본다. n 을 처음부터 다 더해보기도 하고 두 개만 더해보기도 하고..

근데 보니까 n = 4 일 때: 11.. 뭔가 dp[ n - 1 ] + 무언가 가 확실해 보인다. 근데 보니까 dp[n - 2] * 2를 하면 10이다 그리고 이 둘을 더하면 21이고, 같은 방식으로 4도 해보자. 5 + 3 * 2 = 11. 이 점화식이 정답일 확률이 90%로 올라갔다.

 

그리고 이 점화식은 정답이었다.

 

dP[i] = (dp[i - 2] * 2) + dp[i - 1];

 

그리고 long 타입을 사용하지 않기 위해서(메모리) 처음부터 10,007 을 나누 값으로 저장을 하였다.

 

 

 

  풀이

 

 

package src.DP;

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

public class SetTile_Sec {
    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[N + 3];

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


        for(int i = 3; i <= N; i++){
            dp[i] = ((dp[i - 2] * 2) + dp[i - 1]) % 10007;
        }

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


    }
}