[Algorithm] 백준_평범한 배낭_12865번 (JAVA) 🎒

📝문제

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

평범한 배낭_12865번

티어: 골드 5

💡풀이

문제 유형

다이나믹 프로그래밍

 

걸린 시간

60분

 

시간 복잡도

O(NxK)

 

풀이 방법 도출

1. 일단 dp라고 생각도 못했고, 배낭문제 유형이 있다는 것도 몰랐다.. 그래서 문제 이해하는데만 30분 걸린 거 같다
2. 이 블로그 덕분에 겨우 풀 수 있었다.. https://howudong.tistory.com/60

import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //물품 수
        int K = Integer.parseInt(st.nextToken()); //최대 무게

        int[][] 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 = 0 ; j <= K; j++){//j무게의 배낭
                if(j < W){//배낭에 넣을 수 있는 최대 무게 보다 물건의 무게가 클 때 => 배낭에 물건을 넣을 수 없음
                    dp[i][j] = dp[i-1][j];
                }else{//배낭에 넣을 수 있는 최대 무게 보다 물건의 무게가 작거나 같을 때 => 배낭에 물건을 넣을 수 있음
                    dp[i][j] = Math.max(dp[i-1][j], V + dp[i-1][j-W]);
                }
            }

        }
        System.out.println(dp[N][K]);
    }
}

 

🤔Review

어려웠지만 쀼듯해..