[백준] 14728 벼락치기 - 배낭문제(냅색, KnapSack) + DP(Dynamic Programming) JAVA

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

14728번: 벼락치기

코드설명

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

 

일반적인 배낭문제로써, 배낭문제의 로직을 적용하면 해결할 수 있습니다.

시간초과가 발생하기에 dp[101][100001] 을 사용합니다. 각 레벨(101)가지에서의 공부시간별( 100001  )로 최대 점수를  저장합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M, H, T;
	public static int answer = 0;
	public static int[] arr;
	public static int[] studyTime, studyScore;
	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());
    	T = Integer.parseInt(st.nextToken());
    	
    	studyTime = new int[N];
    	studyScore = new int[N];
    	dp = new int[101][100001];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		studyTime[i] = Integer.parseInt(st.nextToken());
    		studyScore[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	System.out.println(simulate(0, T));
	}
	
	public static int simulate(int level, int leftTime) {
		if(leftTime < 0) return 0;
		if(level >= N) return 0;
		if(dp[level][leftTime] > 0) return dp[level][leftTime];
		
		int temp1 = 0;
		if(leftTime - studyTime[level] >= 0) {
			temp1 = studyScore[level] + simulate(level + 1, leftTime - studyTime[level]);
		}
		int temp2 = simulate(level + 1, leftTime);
		
		return dp[level][leftTime] =  Math.max(temp1,  temp2);
	}
	
	
}

 

다르게 풀어본코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
	public static int N, M, C, T;
	public static Study[] study;
	public static int[][] dp;
	public static int answer = 0;
	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());
		T = Integer.parseInt(st.nextToken());
		study = new Study[N];
		dp = new int[N][10001];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int inputK = Integer.parseInt(st.nextToken());
			int inputS = Integer.parseInt(st.nextToken());
			study[i] = new Study(inputK, inputS);
			
			Arrays.fill(dp[i], -1);
		}
		answer = simulate(0, T);
		System.out.println(answer);
	}
	
	public static int simulate(int level, int curT) {
		if(curT < 0) return 0;
		if(level >= N) return 0;
		if(dp[level][curT] != -1) return dp[level][curT];
		if(curT == 0) return 0;
		
		int resultA = 0, resultB = 0;
		if(curT - study[level].K >= 0) {
			resultA = study[level].S + simulate(level + 1, curT - study[level].K);
		}
		resultB = simulate(level + 1, curT);
		
		return dp[level][curT] = Math.max(resultA, resultB);
		
	}
	
}
 
class Study{
	int K;
	int S;
	public Study(int K, int S) {
		this.K = K;
		this.S = S;
	}
}