(Baekjoon) dp - (5) 타일 채우기

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

2133번: 타일 채우기

D(n) = 3*D(n-2) + 2*(D(n-4) + D(n-6) +..... + D(0))

 

 

package dp;

import java.io.IOException;
import java.util.Scanner;



public class _2133{
    static int result = 0;
    static int d[] = new int[100];
    public static int dp(int n){
        
        if(n==0)
            return 1;
        if(n==1)
            return 0;
        if(n==2)
            return 3;
        if(d[n] != 0)
            return d[n];
        result = 3*dp(n-2);

        for(int i = 4 ; i <= n ; i+=2){
            result += 2*dp(n-i);
        }        
        return d[n] = result;       
    
    }

    public static void main(String args[]) throws IOException{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(dp(n));
        
        sc.close();

    }
}

 

홀수인경우는 구할필요없음

점화식을 잘 세우는것이 관건...

이걸 문제유형으로 외워서 푸는건지 아니면 점화식을 직관적으로 세우는사람도 있는지 의아하다.

 

 

 

 

 

 

 

백준문제풀이Github : 

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

sdk0213/baekjoon-study