📝문제

전형적인 knapsack 알고리즘 문제이다.
학교 인공지능 수업 시간에 배운 적이 있는데 구현법이 생각이 나지 않았다.
그래서 처음에는 dfs로 풀어보았다... 하지만 결과는 시간초과
dfs가 시간초과가 나서 dp로 다시 풀어보았다.

가방의 제한 무게를 column으로, 넣을 수 있는 보석 종류를 row로 하는 DP배열을 만든다.
즉, dp[i][j]는 가방의 제한 무게가 j이고 i번째 보석까지 넣을 수 있을 때의 최대 가치이고
문제에서 요구하는 답은 dp[n][k]에 담겨져 있을 것이다.

그럼 이제 어려운 점화식 부분인데,

1. i번째 보석을 담을 수 없는 경우
2. i번째 보석을 담을 수 있는 경우

이렇게 두가지로 나뉜다.

i번째 보석을 담을 수 없는 경우는
현재 가방의 무게 제한 j가 지금 넣으려는 보석(i번째 보석)의 무게보다 작을 때이다.
그때는 i-1번째 보석을 사용했을 때의 최대 가치 값을 그대로 사용한다.
즉, dp[i][j] = dp[i-1][j]

i번째 보석을 담을 수 있는 경우는
해당 보석의 무게만큼 비워내고 보석의 value를 더했을 때와 해당 보석을 넣지 않았을 때의 value를 비교해서 더 큰 값을 사용한다.
즉, dp[i][j] = max(dp[i-1][j-i번째 보석 무게] + i번째 보석 value, dp[i-1][j])

문제를 처음 봤을 때부터 dp알고리즘을 생각했어야 했는데
아직 부족한 부분이 많다😭

📌코드

package Solving;

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

public class BOJ12865 {

    /**
     *  1. dfs로 풀어보자 : time out...
     *  2. dfs를 dp로 바꿔보자
     */

    static int n, k;
    static int[][] comp; // weight, value

    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());
        comp = new int[n+1][2];

        for(int i = 1; i < n+1; i++){
            st = new StringTokenizer(br.readLine());
            comp[i][0] = Integer.parseInt(st.nextToken()); //weight
            comp[i][1] = Integer.parseInt(st.nextToken()); //value
        }

        int[][] dp = new int[n+1][k+1];
        //dp[i][j] : 가방의 제한 무게가 j이고 넣을 수 있는 i번째 보석까지 넣을 수 있을 때의 최대 가치
        for(int i = 1; i < n+1; i++){
            for(int j = 1; j < k+1; j++){
                // 가방의 제한 무게가 넣으려는 보석의 무게보다 가벼울 때: i-1번째 보석을 넣은 dp값 사용
                if(j < comp[i][0]) dp[i][j] = dp[i-1][j];
                // i번째 보석을 넣을 수 있는 경우
                // i번째 보석의 무게를 뺐을 때의 value+i번째 보석 value와 dp[i-1][j]를 비교
                else dp[i][j] = Math.max(dp[i-1][j-comp[i][0]] + comp[i][1], dp[i-1][j]);
            }
        }
        System.out.println(dp[n][k]);
    }
}