이번에 풀어본 문제는
백준 12865번 평범한 배낭 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int N,K;
    static int [][] dp;
    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());

        dp = new int[N+1][K+1];

        for(int i = 1; i <= N; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            for(int j = 1; j <= K; ++j)
            {
                dp[i][j] = j < w ? dp[i-1][j] : Math.max(dp[i-1][j],v + dp[i-1][j-w]);
            }
        }
        System.out.print(dp[N][K]);
    }
}

📝 풀이

N개의 물건들의 무게와 가치가 주어질 때, 가방에 넣을 수 있는 K만큼의 무게로 만들 수 있는 가치의 최댓값을 구하는 문제입니다.
2차원 배열을 활용한 dp로 해결할 수 있습니다.
dp 배열의 행은 입력받은 물건의 번호순서를 의미하며 열은 무게를 의미합니다.
물건의 정보를 입력받으면 이전 값과 비교하여 해당 무게에서의 최댓값을 누적하여 판단할 수 있습니다.
반복문 내의 조건을 보면, j 값이 w보다 작은경우는 현재 탐색중인 무게에 물건을 담을 수 없는 경우이므로, 앞서 구한 dp[i-1][j]값을 저장할 수 있으며, 그 이외의 경우는 현재 입력받은 물건을 담고도 j-w 만큼의 무게가 남았다는 것을 의미하므로, 이전에 dp에 누적했던 값과 현재 주어진 값을 비교하여 더 큰값으로 갱신하도록 해줍니다.
위의 조건으로 K무게까지 누적해주고 마지막 반복의 결과값이 담긴 dp[N][K]값을 출력하면 해결됩니다.

📜 후기

요즘 삼성기출을 돌리고있었는데, 너무 구현문제 위주인것 같아서 평소 취약했던 dp문제를 한번 풀어보았습니다! dp문제는 풀때마다 헷갈리는거같습니다 ㅠ
평범한 배낭은 아닌것같네요 ..ㅋㅋ