[백준 12865번][Java] 평범한 배낭 - 점화식과 구현의 관계

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

이 글의 초점은 문제 풀이에 있지 않다. 그러므로 바로 본론으로 들어가겠다.

이 문제의 점화식은 다음과 같다.

 

아직 몇 문제 풀어보진 않았지만 지금까지 풀어본 DP 문제들은 '완전 탐색의 바텀-업 버전'이었다.

이런 문제들은 완전 탐색을 바텀업으로 구현하기 위해 점화식을 세울 필요가 있다. 

이 점화식도 그냥 하늘에서 떨어지는게 아니라 완전 탐색의 형태를 수식의 형태로 바꿨을 뿐이다.

 

내가 이 문제를 풀면서 약간의 괴리가 느껴졌던 건(내가 재귀로 푸는 방식에 익숙하기 때문이기도 하다.)

dp[i][k] 라는 식을 이중 for문을 돌리면서 어떻게 답을 찾아가는지 이해가 되지 않았기 때문이다.

 

예를 들자면 만약 dp[i] = dp[i-1] +1이라는 점화식이 있다고 하자. 그렇다면 우리는 간단하게 for문을 아래처럼 구성할 수 있다.

for(int i = 1; i < n; i++) {
	dp[i] = dp[i-1] + 1;
}

이건 쉽게 이해가 됐다. i를 늘려가면서 i-1 값을 이용해 값을 만들어가는게 눈에 확 띈다.

 

 

이 문제도 점화식에 대한 감은 잡았지만 구현으로 연결이 돼지 않아, 결국 다른 풀이를 참고해 작성했다.

for (int i = 1; i <= n; i++) {
	for (int j = k; j >= 0; j--) {
    	dp[i][j] = dp[i-1][j];
			if(j - items[i].w >= 0) dp[i][j] = Math.max(dp[i][j] , dp[i-1][j-items[i].w] + items[i].v);			
	}
}

위 구현에서처럼 dp[i][k] = max(dp[i-1][j], dp[i-1][k-w[i]] + v[i]) 인 점화식을 구하는데 왜 k를 0이 될 때까지 모든 범위에 걸쳐서 다 구하는거지?  라는 이상한 질문이 생겼다. 

차원이 하나 더 늘었을 뿐인데 감이 잡히지 않았다. 

 

이상한 물음이었지만 나한테는 꽤 중요했다. 다음의 그림을 통해 답을 얻었다.

2차원 dp배열

이 문제의 2차원 dp 배열은 위와 같은 방식으로 답을 쌓아 나간다.

i=0에서 모든 j범위에서 답을 구하고 이를 이용해 i=1에서 이 값들을 이용해 또 모든 값을 계산한다.

이런 방식이 이어진다. 

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/*
평범한 배낭
https://www.acmicpc.net/problem/12865
 */
public class Main {
	static int n,k;
	static Item[] items;
	static int[][] dp;
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		StringTokenizer st = new StringTokenizer(reader.readLine());
		n = Integer.parseInt(st.nextToken()); k = Integer.parseInt(st.nextToken());
		items = new Item[n+1];
		dp = new int[n+1][k+1];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(reader.readLine());
			int w = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			items[i] = new Item(w,v);
		}

		int ret = solve();
//		for (int i = 0; i <= n; i++) {
//			System.out.println(Arrays.toString(dp[i]));
//		}
		System.out.println(ret);
	}

	private static int solve() {
		for (int i = 1; i <= n; i++) {
			for (int j = k; j >= 0; j--) {
				dp[i][j] = dp[i-1][j];
				if(j - items[i].w >= 0)
					dp[i][j] = Math.max(dp[i][j] , dp[i-1][j-items[i].w] + items[i].v);
			}
		}
		return dp[n][k];
	}
}
class Item {
	int w,v;
	public Item(int w, int v) {
		this.w = w;
		this.v = v;
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}