(Java) 백준 12865 - 평범한 배낭

2022. 7. 12. 02:07·코딩 테스트

문제 이름은 평범한 배낭이지만 전혀 평범하지 않다고 느꼈다.

한참을 고민하다가 검색을 했지만 너무 어려웠다.

대표적인 DP 문제라고 하는데 knapsack 알고리즘을 이용해서 풀어야 한다.

 

입력값을 w 배열과 v 배열에 삽입하고 각 무게와 가치를 계산해서 dp배열에 가치의 최댓값을 넣어주면 된다.

가장 이해하기 어려웠던 부분은 아래의 코드인데

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);

이전에 계산했던 가치, 남은 무게의 가치 + 현재 가치 중 큰 값을 저장하는 부분이다.

j - w[i] 는 j의 무게에서 현재 아이템의 무게를 뺀 값이다. 이 값은 dp[i-1][j - w[i]] 에 이미 저장되어 있고

이 값에 현재 아이템의 가치를 더한 값과 이전에 저장했던 값중 최대값이 dp[i][j[가 되는 것이다.

 

코드는 간단하지만 혼자서는 구현하지 못했고 해설을 봐도 이해하기 정말 어려웠던 문제였다.


최종 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        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[] w = new int[n + 1];
        int[] v = new int[n + 1];

        // 입력값 각 배열에 삽입
        for (int i = 1; i < n + 1; i++) {
            st = new StringTokenizer(br.readLine());
            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[n + 1][k + 1];

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < k + 1; j++) {
                // 이전까지 계산했던 가치를 저장
                dp[i][j] = dp[i - 1][j];
                // j의 무게에서 현재 아이템의 무게를 뺐을때 남는 무게가 존재한다면
                if (j - w[i] >= 0) {
                    // 이전에 저장한 값, 남은 무게의 가치 + 현재 가치중 큰 값을 저장
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                }
            }
        }

        System.out.println(dp[n][k]);
    }
}

 

'코딩 테스트' 카테고리의 다른 글

(Java) 프로그래머스 - 멀쩡한 사각형  (0) 2022.07.14
(Java) 프로그래머스 - 게임 맵 최단거리  (0) 2022.07.12
(Java) 백준 1932 - 정수 삼각형  (0) 2022.07.11
(Java) 프로그래머스 거리두기 확인하기  (0) 2022.07.09
(Java) 백준 11053 - 가장 긴 증가하는 수열  (0) 2022.07.08
'코딩 테스트' 카테고리의 다른 글
  • (Java) 프로그래머스 - 멀쩡한 사각형
  • (Java) 프로그래머스 - 게임 맵 최단거리
  • (Java) 백준 1932 - 정수 삼각형
  • (Java) 프로그래머스 거리두기 확인하기
로승리
로승리
  • 로승리
    Roy's Blog
    로승리
  • 전체
    오늘
    어제
    • 분류 전체보기
      • Issuefy
      • Language
      • Spring
      • Database
      • Network
      • Kubernetes
      • AWS
      • 코드스쿼드
      • 코딩 테스트
      • 생각정리
      • 국비지원
      • 회고
      • 컨퍼런스, 세미나
  • 블로그 메뉴

    • 홈
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
로승리
(Java) 백준 12865 - 평범한 배낭
상단으로

티스토리툴바