[백준] 12855 평범한 배낭 - JAVA

1. 문제유형 : DP

2. 시간복잡도 : O(NK)

 

해당 문제는 단순히 DFS로 풀었다가 시간초과가 발생하여 DP로 방향을 전환한 문제다. 그러나 방법이 생각나지 않아서 구글링의 힘을 빌렸다.

 

(K+1)*N 의 cache배열을 생성한 뒤, 무게가 0~K일 때의 최대 가치를 누적해서 저장한다. 해당 누적 데이터는 여러 아이템을 가방에 넣을 수 있는 무게가 되었을 때 사용된다.

 

예를들어, 문제의 예제와 같은 경우 무게가 0~6인 경우 각각 하나의 아이템만 가져갈 수 있지만, 7인 경우에는 (4, 8),  (3, 6) 아이템을 가져갈 수 있다.

이때, (3, 6)의 index가 2이므로 cache[7][2]에 저장되는데, 해당 값은 아래와 같이 구할 수 있다.

cache[7-3][2-1]

즉, 무게가 3인 (3, 6) 아이템과 무게가 4(7-3)인 item을 하나 선정하는 건데, cache에는 누적하여 최대 값을 저장하기 때문에 바로 이전 인덱스인 1(i-1)를 찾아가면 된다. cache[4][1] = 8

따라서 cache[7][i] = Math.max(cache[7][i-1], items[i][1] + cache[7-items[i][0]][i-1]) 이 된다.

 

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

public class Main {

	public static int N, K, items[][], cache[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		items = new int[N][2];
		cache = new int[K+1][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			items[i] = new int[]{ Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) };
		}

		for (int i = 1; i <= K; i++) {
			for (int j = 0; j < N; j++) {
				int prev = j == 0 ? 0 : cache[i][j-1];
				if(i-items[j][0] < 0) {
					cache[i][j] = prev;
				}else if(i-items[j][0] == 0) {
					cache[i][j] = Math.max(prev, items[j][1]);
				}else {
					cache[i][j] = Math.max(prev, j==0 ? items[j][1] : cache[i-items[j][0]][j-1] + items[j][1]);
				}
			}
		}
		
		System.out.println(cache[K][N-1]);
	}

}