[백준] 2240 자두나무 - KnapSack(냅색, 배낭문제) + DP(Dynamic Programming) + 완전탐색(Brute Force) JAVA

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

2240번: 자두나무

코드설명

 KnapSack(냅색, 배낭문제) + DP(Dynamic Programming) + 완전탐색(Brute Force) 를 활용하는 문제입니다.

 

문제에서 가장 중요한점은, 문제의 시간복잡도를 고려하는 것 입니다.

문제에서 총 탐색하는 횟수는 2가지의 W를 총 30번 선택하고, Level 은 1000 입니다. 2^30 의 가짓수가 나옵니다.

2^30 = 1,073,741,824, 10억입니다. 약 10초가 걸릴 것입니다.

 

그러모르 DP는 필수적입니다. DP[현재시각, 초][현재 선택횟수 W][몇번쨰 위치인가를

public static int[][][] dp = new int[1001][31][3];

이와 같이 표현합니다.

 

제가 실수했던 부분은 다음과 같습니다.

1. 자두의 위치는 처음에 1번 자두나무 아래에 위치해있다.

이 문제의 조건을 보고, 처음에 자두가 바로 위치를 바꾸는경우를 고려하지 못했습니다.무조건 1초에는 자두나무 1번에 있는것이 아닌, 1초에 W를 한번 사용해서 자두나무 2번에 있을 수 있습니다.이 부분에서 틀린 분들이 많을 것 같습니다.

answer = Math.max(simulate(0, 0, 1), simulate(0, 1, 2));

 

2. simulate함수 내에서 DP의 변수 잘못사용

아래의 코드가 맞지만 처음에는 dp[level][W][curPos]로 사용하여 당연히 틀렸었습니다. 

if(dp[level][curW][curPos] != -1)
    return dp[level][curW][curPos];

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int N, M, P, T, W;
	public static int answer = 0;
	public static int[] jaduTree = new int[1001];
	public static int[][][] dp = new int[1001][31][3];
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	T = Integer.parseInt(st.nextToken());
    	W = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<T;i++) {
    		st = new StringTokenizer(br.readLine());
    		jaduTree[i] = Integer.parseInt(st.nextToken()); 
//    		System.out.println("jaduTree[i]:"+jaduTree[i]);
    	}
    	
    	for(int i=0;i< 1001;i++) {
    		for(int j=0;j< 31;j++) {
    			for(int k=0;k<3;k++) {
    				dp[i][j][k] = -1;
    			}
    					
    		}
    	}
    	
    	answer = Math.max(simulate(0, 0, 1), simulate(0, 1, 2));
    	System.out.println(answer);
    	
    }
    
    public static int simulate(int level, int curW, int curPos) {
    	if(level == T) { //T번 떨어질경우 종료.
//    		System.out.println(sum);
//    		answer = Math.max(answer, sum);
    		return 0;
    	}
    	
    	if(dp[level][curW][curPos] != -1)
    		return dp[level][curW][curPos];
    	
    	//안움직이는경우
    	int temp1 = 0, temp2 = 0;
    	temp1 = ( jaduTree[level] == curPos ? 1 : 0 ) + simulate(level + 1, curW, curPos );
    	
    	//움직이는 경우
    	if(curW + 1 <= W)
    		temp2 = ( jaduTree[level] == curPos ? 1 : 0 ) + simulate(level + 1, curW + 1, curPos == 1 ? 2 : 1 );
    	
    	return dp[level][curW][curPos] = Math.max(temp1,  temp2);
    }
    
}