백준 12685 : 평범한 배낭 java

링크

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

12865번: 평범한 배낭

 

풀이

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

public class back_12685 { // 평범한 배낭

	static int n, k;
	static int dp[][]; // dp 배열
	static int w[], v[]; // 무게, 가치 배열

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] temp = br.readLine().split(" ");
		
		n = Integer.parseInt(temp[0]);
		k = Integer.parseInt(temp[1]);
		
		dp = new int[n+1][k+1];
		
		w = new int[n+1];
		v = new int[n+1];
		
		for(int i=0; i<n; i++) {
			temp = br.readLine().split(" ");
			w[i] = Integer.parseInt(temp[0]);
			v[i] = Integer.parseInt(temp[1]);
		}
		
		// dp 만들기
		for(int i=1; i<=n; i++) { // i -> 1,2,3 ... n
			for(int j=1; j<=k; j++) { // j -> 1,2,3 ... k
//				System.out.println("dp[i-1][j]="+dp[i-1][j]);
				dp[i][j] = dp[i-1][j];
				if(j>=w[i]) { 
					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
				}
//				System.out.println("=====================");
//				for(int a=0; a<dp.length; a++) {
//					for(int b=0; b<dp[a].length; b++) {
//						System.out.print(dp[a][b] + " ");
//					}
//					System.out.println();
//				}
//				System.out.println("=====================");
			}
		}
		System.out.println(dp[n][k]);
	}

}

 

 

꼭 다시 풀어볼 문제!!!!!!

DP배열 사용하는데 아직 이해가 부족한듯 하다.