[백준] 11727 2nx 타일링 2 - 동적계획법(DP, Dynamic Programming) JAVA

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

11727번: 2×n 타일링 2

코드설명

DP 문제입니다.

 

2x1 타일링일시

모양 : | 

1개입니다.

 

2x2 타일링 일시

모양 : || = ㅁ

3가지입니다.

 

2x3 타일링일시

모양 : |=, |ㅁ, |||, =|, ㅁ|

5가지입니다.

 

규칙을 확인할 수 있습니다.

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

 

그림을 그릴때 각 조건을 만족하도록 그 전의 모양을 기준점으로 잡고 그리면 규칙을 찾는데 도움이 됩니다.

코드

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

public class Main {
	public static int T, N;
	public static int answer = 0;
	public static int[] arr;
	public static int[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	arr = new int[1001];
    	dp = new int[1001];
    	
    	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]);
    }
    
}

코드 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int N, T, K, M;
    private static int answer = 0;
    private static int[] arr;
    private static final int MOD = 10007;
    private static int[] cache;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		cache = new int[N + 1];
		Arrays.fill(cache, -1);
		System.out.println(tile(N));
		
    }
    
    private static int tile(int n) {
    	//기저사례 : 
    	if(n <= 1) return 1;
    	if(cache[n] != -1) return cache[n];
    	int ret;
    	ret = (tile(n - 1) + tile(n - 2) + tile(n - 2)) % MOD;
    	
    	return cache[n] = ret;
    }
    
    
    
}