🔗 Problem

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

👩‍💻 Code

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

// 평범한 배낭

public class BJ12865 {
	
	static int n;
	static int k;
	static int[] weight;
	static int[] value;
	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());
		k = Integer.parseInt(st.nextToken());
		weight = new int[k + 1];
		value = new int[n];
		dp = new int[k + 1];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			weight[i] = w;
			value[i] = v;
			
			for(int j = k; j >= w; j--) {
				dp[j] = Math.max(v + dp[j - w], dp[j]);
			}
		}
		
		System.out.println(dp[k]);
	}

}

📌 Note

아이디어

• 행: n번째 물건 / 열: 1~k까지 무게
• n번째 물건의 w, v에 대하여 w 이상인 열에는 해당 물건을 담을 수 있으므로
  dp를 업데이트 해주었다.

틀렸습니다

• 처음에 행렬 곱셈 순서 구하는 문제처럼 생각해서 dp 점화식을 잘못 세웠다.

---

✔ 3일 후 다시 풀어보았다.

• 어제 #2293을 풀어서 해당 문제도 일차원 배열로 구현할 수 있는 것을 캐치하여 더 깔끔하게 풀 수 있었다.
• 코드는 새로운 풀이로 업데이트함
• 이중 for문 중 안 쪽 for문에서 j = k부터 거꾸로 내려갔는데,
  만약 j = w부터 올라가게 된다면 weight * 2 == j인 순간
  즉, 무게가 3인 물건에 대하여 무게의 총합이 6이 되는 순간은
  3과 6-3 == 3과 3이 되어서 3을 두 번 담게 된다.
  이와 같은 상황을 방지하기 위해 k부터 내려가는 방식으로 구현하였다.