[백준] 동적 프로그래밍 - 12865번 평범한 배낭(Java)

문제링크

12865번: 평범한 배낭

 

접근한 방법

• 동적 프로그래밍

 

---

풀이방법

처음에 1차원 배열로 계산하여.. 실패하였다..

다른 블로그들을 보며 아래 소스코드 작성 방법을 참조하여 문제를 풀었다.

---

소스코드 작성 방법

• a를 이중 배열로 선언
  크기는 [n+1][k+1]로
• i는 물건의 종류, j는 무게
• a[i][j]에 i-1번째 물품을 넣었을 때의 가치를 넣음
• (현재(j) 무게 - 물품의 무게) > 0 이라면
  max(i번째 물건을 안 넣을 경우, i번째 물건을 넣을 경우)
  
  

실수한점

• 입력받을 인덱스를 0부터 한 것
• 입력받을 배열의 크기를 모두 n으로 설정했던 것 (복사-붙여넣기의 폐해..)

소스코드

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    public static int solution(int n, int k, int[] w, int[] v) {
        int[][] a = new int[n+1][k+1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                a[i][j] = a[i - 1][j];
                if (j - w[i] >= 0) {
                    a[i][j] = Math.max(a[i - 1][j], a[i - 1][j - w[i]] + v[i]);
                }
            }
        }

        return a[n][k];
    }

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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[k+1];
        for(int i=1 ; i<=n ; i++){
            st = new StringTokenizer(br.readLine());
            w[i] = Integer.parseInt(st.nextToken()); // 무게
            v[i] = Integer.parseInt(st.nextToken()); // 가치
        }

        bw.write(solution(n,k,w,v)+"\n");

        br.close();
        bw.close();

    }

}