(Baekjoon) dp - (2) 2×n 타일링 2

 

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

우선 내가 주어진 문제가 시험문제이고 DP라는 가정이 있다면 

위와같은 가정으로 추론으로 점화식을 풀수있다.

 

하지만 점화식이 최적의 답인지 아니면 그리디알고리즘에서 더 빨리 찾는법이 있는지

아니면 그외에 더 최적의 알고리즘이 있는지는 경험이 늘어나봐야 알것같다.

package dp;

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

public class _11727{
    
    static int d[] = new int[1001];
    public static int dp(int x){
        if(x == 1) return 1;
        if(x == 2) return 3; 
        if(d[x] != 0) return d[x];
        return d[x] = ((2*dp(x-2)) + dp(x-1)) % 10007;

    }
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println(dp(Integer.parseInt(br.readLine())));

    }

}

 

 

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study