[백준] 1904 01타일 - 동적계획법(Dynamic Programming, DP) JAVA

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

1904번: 01타일

코드설명

동적계획법(Dynamic Programming, DP) 문제입니다.

 

문제를 이해해보면, 1, 00 이라는 타일을 활용하여서 타일을 조합할 수 있습니다.

문제에서 먼저 점화식을 구해야합니다.

F(i) = F(i+1) + F(i+2) 라는 점화식이 나옵니다. 

여기서 F(i+1)이란 F(i)라는 숫자에 1을 붙인다는 의미입니다.

F(i+1)이란 F(i)라는 숫자에 00 을 붙인다는 의미입니다.

 

처음에 재귀로 모든 경우의수를 구하는경우, 시간초과 발생합니다. 모든 경우를 다 구합니다.

이와 같은경우

simulate(0) = simulate(1) + simulate(2)

simulate(1) = simulate(2) + simulate(3)

simulate(3) = simulate(4) + simulate(5)

...

이렇게 보면 simulate함수가 계속 겹치고 있습니다.

그렇기에 DP를 활용하여 simulate()값이 겹치는 부분을 메모리제이션하여 진행합니다.

 

재귀를 활용하지않고 반목문을 활용한 방식도 구해보았습니다.

시간 상으로는 반복문이 훨씬 더 빠릅니다. 스택 프레임을 사용하지 않아서 그런 결과같습니다.

 

먼저, tile(int n) : n개의 타일이 남았을떄 만들 수 있는 모든 가짓수를 반환한다. 를 정의하여 사용합니다.

 

구현하면서 실수했던 점입니다.

1. 처음에는 if(n <= 2) return 1; 으로 기저사례를 처리했었는데, 2개가 남은경우에 1개로 두가지를 채울 수 있으므로 <= 1 로 처리해야 누락되지 않고 처리가 가능합니다. (1 타일의 길이는 1이고, 00 타입의 길이는 2 이므로 2가지가 남았을 경우 타일과 00타일 둘다 채울 수 있어서 n < = 2로 할경우 세지 않는경우가 존재합니다.)

 

코드

 

재귀와 DP를 활용하여 해결할경우

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

public class Main {
	public static int N;
	public static int answer = 0;
	public static int[] DP;
	public static StringBuilder sb = new StringBuilder();
	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[N+2];
    	System.out.println(simulate(0) %15746);
    	
    	System.out.println(sb.toString());
	}
	
	public static int simulate(int level) {
		//종료조건
		if(DP[level] > 0) return DP[level]%15746;
		if(level == N) return 1; //만들 수 있는 경우이기에 + 1 처리합니다.
		if(level > N) return 0;
		
		return DP[level] = simulate(level + 1) %15746 + simulate(level + 2) %15746; //1타입을 앞에 붙이는경우와 00 타일을 붙이는경우로 나뉩니다. 
	}

}

 

더 깔끔한 코드 2.

import java.util.*;
import java.io.*;

public class Main {
    public static int N, M;
    public static int answer = 0;
    public 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));
	}
    
    public static int tile(int n) {
    	if(n <= 1) return 1;
    	if(cache[n] != -1) return cache[n];
    	
    	return cache[n] = (tile(n - 2) + tile(n - 1)) % 15746;
    }
    
}

 

 

반복문을 활용할경우

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

public class Main {
	public static int N;
	public static int answer = 0;
	public static int[] DP;
	public static StringBuilder sb = new StringBuilder();
	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[N+2];
    	DP[0] = 0; //
    	DP[1] = 1; //"1" 
    	DP[2] = 2; //"00", "11"
    	for(int i=3; i<=N; i++) {
    		DP[i] = DP[i-1] % 15746 + DP[i-2] % 15746; 
    		DP[i] %= 15746;
    	}
    	System.out.println(DP[N]);
	}

}