[백준/JAVA] 12865번: 평범한 배낭

🔺 문제

12865번: 평범한 배낭

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public 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[][] item = new int[N + 1][2];
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            item[i][0] = Integer.parseInt(st.nextToken());   // 무게
            item[i][1] = Integer.parseInt(st.nextToken());   // 가치
        }
        
 
        int[][] dp = new int[N + 1][K + 1];
        
        for(int k = 1 ; k <= K ; k++) { // 무게
            for(int i = 1 ; i <= N ; i++) { // item
                dp[i][k] = dp[i - 1][k]; // 기본적으로 이전 아이템의 가치 저장
                
                if(k - item[i][0] >= 0) { // 무게가 남는다면
                    dp[i][k] = Math.max(dp[i - 1][k], item[i][1] + dp[i - 1][k - item[i][0]]); // 이전 아이템에서 구한 가치 vs (자신의 가치 + 남은 무게의 자치) 中 큰 값 선택
                }
            }
        }
        
        System.out.println(dp[N][K]);
    }
}

✅ 해결 아이디어
✔ DP. 배낭 알고리즘
- 짐을 쪼갤 수 없다!
- dp[아이템 idx][무게] = 가치

 

---

🔺 다른 풀이들

- 진짜 상세한 설명 & 마지막에 적어두신 글 보고 좀 용기를 얻었다,,,😭

[백준알고리즘-JAVA]12865번 풀이(평범한 배낭) - 초보도 이해하는 풀이

 

 

- 읽고 좀 점화식 이해가 됐다,,, 미쳤다,,, (복습용)

[백준,BOJ 12865] 평범한 배낭(JAVA 구현, 추가풀이)

 

 

- 과정 설명 굿,, 이해 완!!!

[백준] 12865번 평범한 배낭 (자바 풀이)

---

💬 느낀 점

어렵지만 포기하지말고 해설이 익숙해질때까지 똑같이 풀어보자,,,

이해가 어려우면 익숙해지고 이해하자,,,,,😵😵

(출처: 인포돈님 글 인용 https://infodon.tistory.com/80)

 

Knapsack  문제 좀,,, 더 찾아보고 풀어봐야겄다

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준,BOJ 12865] 평범한 배낭(JAVA 구현, 추가풀이)

[백준알고리즘-JAVA]12865번 풀이(평범한 배낭) - 초보도 이해하는 풀이