BOJ_G5_12865

📁 [G5_12865] 평범한 배낭

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
    static StringTokenizer st;
    static int N, K;
    public static void main(String[] args) throws IOException {
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine(), " ");

        // 물품의 수
        N = Integer.parseInt(st.nextToken());

        // 버틸 수 있는 무게
        K = Integer.parseInt(st.nextToken());

        // 무게와 가치 저장 배열
        int[][] arr = new int[N+1][2];

        // 물품의 무게 , 1~k 까지의 무게 , 값은 가치 누적이다
        int[][] dp = new int[N+1][K+1];

        for(int i=1; i<=N; i++){
            st = new StringTokenizer(br.readLine(), " ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<=N; i++){
            for(int j=1; j<=K; j++){

                // 들어갈 수 있는 무게인 경우
                if(j - arr[i][0] >= 0){
                    // dp에 저장된 누적 값과 현재 자신의 가치와 남은 무게의 가치를 비교하여 큰 값을 저장한다
                    dp[i][j] = Math.max(dp[i-1][j], arr[i][1] + dp[i-1][j-arr[i][0]]);
                }
                // 들어갈 수 없는 무게면 전행의 값을 가져온다
                else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        System.out.println(dp[N][K]);
    }
}

🤔 나의 생각

이 문제는 대표적인 knapsack 알고리즘을 사용하는 문제이다.
문제에 무게와 가치가 나온다면 99% knapsack 알고리즘을 사용해야한다.
이 문제는 dp 배열에 아이템의 무게와 1~K까지의 무게에 가치를 저장한다.
가방에 들어갈 수 있는 무게이면 dp 배열의 누적값과 현재 자신의 가치와 남은 무게의 가치를 비교하여 큰 값을 저장한다.
이 과정을 반복해 가장 최고 가치를 출력해 낸다.
처음에 혹시나 해서 부분집합의 합으로 풀어봤는데 바로 시간초과가 떠버렸다.
DP문제는 확실히 수학적으로 잘 생각해서 구현해야하는 것 같다. 여러 알고리즘을 알고 있는 것도 중요하다 !!