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

1. 우선 dp안쓰고 재귀함수를 썼었다.

pack(int i, int w) 는 i번째 물건을 현재 무게 w인 백팩에 넣었을 때의 가치, 넣지 않았을 때의 가치 중 더 큰 값을 반환한다!

(근데 이거 틀린 코드다. 이유는 밑에ㅎ)

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

public class boj12865 {
    public static int[] W;
    public static int[] V;
    public static int N, K;
    public static int pack(int i, int w) {
        if(i == N) return 0;
        int v1=0, v2;
        if(w+W[i]<=K) {
            v1 = V[i] + pack(i + 1, w + W[i]);
        }
        v2 = pack(i + 1, w);
        return Math.max(v1, v2);
    }
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken()); // 물품의 수 N(1 ≤ N ≤ 100)
            K = Integer.parseInt(st.nextToken()); // 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)
            W = new int[N];
            V = new int[N];
            for(int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                W[i] = Integer.parseInt(st.nextToken());
                V[i] = Integer.parseInt(st.nextToken());
            }

            br.close();
            bw.write(Integer.toString(pack(0, 0)));
            bw.flush();
            bw.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

따란!

2. 그리고 나서 pack()안에서 dp를 썼다. 이런식으로 👇🏻

    public static int pack(int i, int w) {
        if(i == N) return 0;
        if(dp[i][w] != -1)
            return dp[i][w];
        int v1=0, v2;
        if(w+W[i]<=K) {
            v1 = V[i] + pack(i + 1, w + W[i]);
        }
        v2 = pack(i + 1, w);
        return dp[i][w] = Math.max(v1, v2);
    }

근데 제출하니까 런타임 에러가 뜨는 것..은 내 맘을 아푸게 해..

바보가 조건 설정을 제대로 안해서 그런 거였음 ㅎ

// 잘못 짠 코드
public static int pack(int i, int w) { // i: 물건 인덱스, w: 현재까지의 배낭 무게
    if(i == N) return 0; // 물건 N개를 다 넣어봤으면 탈출
    // 근데 무게에 대한 조건을 안썼네 ^^?    
    if(dp[i][w] != -1)
        return dp[i][w];
    int v1=0, v2;
    if(w+W[i]<=K) {
        v1 = V[i] + pack(i + 1, w + W[i]); // i번째 물건을 담았을 때의 가치 최댓값
    }
    v2 = pack(i + 1, w); // 담지 않았을 때의 가치 최댓값
    return dp[i][w] = Math.max(v1, v2); // 둘 중에 더 큰 걸로 저장
}

배낭이 다 찼을 때는 물건을 더 넣을 수 없으니까 return 0을 해줘야한다. 🤗 히히 그래서 처음에 if(w >= K) return 0; 을 써주면 해결이 된다.

정답 코드.. 후

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class boj12865 {
    public static int N, K;
    public static int[] W, V;
    public static int[][] dp;
    public static int pack(int i, int w) { // i: 물건 인덱스, w: 현재까지의 배낭 무게
        if(i == N) return 0;
        if(w>=K) return 0;
        if(dp[i][w] != -1)
            return dp[i][w];
        int v1=0, v2;
        if(w+W[i]<=K) {
            v1 = V[i] + pack(i + 1, w + W[i]); // i번째 물건을 담았을 때의 가치 최댓값
        }
        v2 = pack(i + 1, w); // 담지 않았을 때의 가치 최댓값
        return dp[i][w] = Math.max(v1, v2); // 둘 중에 더 큰 걸로 저장
    }
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            Scanner sc = new Scanner(System.in);
            N = sc.nextInt(); // 물품의 수 N(1 ≤ N ≤ 100)
            K = sc.nextInt(); // 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)
            W = new int[N];
            V = new int[N];
            dp = new int[100][100000]; // dp[i][w] 에 pack(i, w)를 저장할 것임
            for(int i = 0; i < 100; i++)
                Arrays.fill(dp[i], -1);

            for(int i = 0; i < N; i++) {
                W[i] = sc.nextInt();
                V[i] = sc.nextInt();
            }
            System.out.println(pack(0,0));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

오답노트 끝..

---

+) 처음 코드랑 마지막 코드랑 입출력 방식이 다른데, 이게 왜 이렇게 됐냐,, 하믄

런타임에러 뜨고 다른 사람에게 질문을 했었는데, 그 사람이 BufferedReader랑 BufferedWriter를 쓰는 게 불편하니까 먼저 System.out, 스캐너를 써보고, 시간 초과가 나면 바꾸는 게 나을 거라고 말해줬다! 그래서 바꿔봤는데 내 생각이랑 다른 결과가 나왔다.

1) Scanner, System.out.println 사용
2) BufferedReader, System.out.println 사용
3) BufferedReader, BufferedWriter 사용

2번이 젤 빨랐다. 앞으로는 2번을 기본으로 하고 풀어야징 😙 키킼