[백준/BOJ] 12865 평범한 배낭

[백준/BOJ]

문제 # https://www.acmicpc.net/problem/12865

 

 

 

 

 

내가 작성한 코드

package boj;
import java.io.*;
import java.util.*;


public class BOJ12865 {
	static int N, K;
	static int[][] dp;
	static int[] w;
	static int[] v;
	public static void main(String[] args) throws Exception{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String[] input = reader.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		K = Integer.parseInt(input[1]);
		
		dp = new int[N+1][K+1];
		w = new int[N+1];
		v = new int[N+1];
		for(int i=1; i<=N; ++i) {
			input = reader.readLine().split(" ");
			w[i] = Integer.parseInt(input[0]);
			v[i] = Integer.parseInt(input[1]);
		}
		
		for(int i=1; i<=N; ++i) {
			for(int j=1; j<=K; ++j) {
				if(j - w[i] >= 0) {
					dp[i][j] = Math.max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]);
				}else {
					dp[i][j] = dp[i-1][j];
				}
			}
		}

		System.out.println(dp[N][K]);
	}

}

 

풀이 및 배운 점

dp[i][j]는 i 번째까지 물건을 선택할 수 있는 경우,  j를 넘지 않는 무게로 얻을 수 있는 최대 가치를 말한다.

 

처음에 Item이라는 class를 선언하여 ArrayList<Item> items로 각각의 무게와 가치를 입력받았는데, 작성하면서 코드가 길어지고 가독성이 좋지 않다는 것을 느꼈다.

그리고 j - w[i] < 0일 때 continue로 넘겨주어 dp[i][j]에 dp[i-1][j]의 경우가 들어가지 않아 답이 도출되지 않아 애를 먹었다.