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

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

11726번: 2×n 타일링

코드설명

문제의 규칙을 찾아내서 진행하는 DP문제입니다.

 

n=1 일떄, 2x1 타일링은

1개

 

n=2일때, 2x2 타일링은

2개

 

n=3일때, 2x3 타일링은

3개

 

n=4 일때, 2x4 타일링은

5개 

 

n=5 일떄, 2x5 타일링은

8개 입니다.

 

N이 1씩 늘어날때마다 피보나치 수열의 특징을 볼 수 있습니다.

피보나치 수열의 식은

dp[N] = dp[N-1] + dp[N-2] 입니다.

해당 수열식을 코드로 구현하면 답입니다.

 

또한, 10007 을 마지막에 계산하는것이 아닌 식마다 적용해줍니다.

코드

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[] 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());
    	
    	dp = new int[11];
    	
    	dp[1] = 1;
    	dp[2] = 2;
    	
    	
    	for(int i=3;i<=N;i++) {
    		dp[i] = dp[i-1] + dp[i-2]; 
    	}
    	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)) % MOD;
    	
    	return cache[n] = ret;
    }
    
    
    
}