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

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


public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[][] dp; // 마지막 상자가 i번째인 가장 큰 가치 .
		int[] weight;
		int[] value;

		for (int k = 1; k <= 1; k++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			weight = new int[N + 1];
			dp = new int[N + 1][K + 1];
			value = new int[N + 1];

			for (int i = 1; i <= N; i++) {
				st = new StringTokenizer(br.readLine());
				weight[i] = Integer.parseInt(st.nextToken());
				value[i] = Integer.parseInt(st.nextToken());
			}
//			System.out.println(weight[0]);
			for(int i = 1 ; i <= K; i++) {
				if(weight[1] <= i) {
					dp[1][i] = value[1];
				}
			}
			for(int i = 2; i < N  + 1; i++) {
				for(int j = 1 ; j <K + 1 ; j++) {
					dp[i][j] = dp[i-1][j];
					if(j >= weight[i]) { //i번째 인덱스를 넣을수 있다면
						dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]); // i번째 인덱스 넣은 가치 + i번째 인덱스의 무게를 뺀만큼의 가치 구한다 .
					}
				}
			}
			System.out.println(dp[N][K]);
//			for(int i = 1 ; i <= N; i++) {
//				for(int j = 1 ; j < K + 1 ; j++) {
//					System.out.print(dp[i][j]+ " ");
//				}
//				System.out.println();
//			}
		}
	}
}

 

dp 알고리즘 하면 알려져있는 가장 대표적인 문제로

2차원 dp배열을 생성하고 점화식을 작성하면 직관적으로 해결할수 있는 문제이다.