[Java] BOJ12865, 백준 - 평범한 배낭

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

12865번: 평범한 배낭

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	39320	14852	9767	36.224%

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

 

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

 

 

<풀이>

문제 자체는 이해하기 어렵지 않다.

주어지는 N개의 물건들 중에서 몇 개를 골랐을 때, 무게가 K가 넘지 않도록 하는 선에서 최대 가치 갖도록 물건을 고르면 되는 아주 간단한 문제이다.

 

그런데 이 문제를 풀면서 아주 중요한 주의사항이 있다. 나는 이것때문에 몇 번을 틀렸다는... 그것은 바로

"같은 물건을 또 넣지 않도록 해야한다" 는 점이다.

 

처음에 생각한 풀이는,

int[] dp배열을 만들어서, dp[i]가 무게 i까지 넣을 수 있는 물건의 가치합 중 최대 가치 합을 저장해주려고 했다.

 

 

예를 들어 왼쪽의 예시같은 경우에는

무게(i)	1	2	3
최대가치(dp[i])	2	9	12

다음과 같이 될 것이다.

 

순서대로 이렇게 되는 과정을 알아보도록 하자

참고로 인덱스 i는 1부터 n까지 사용했다.

클릭하면 움짤로 볼 수 있음

오른쪽의 최대가치(dp[i])를 변경할 때는 dp배열에서 지금 물건을 넣을 수 있는 경우(즉, 무게+인덱스 <= K)를 일일히 비교하여 최댓값으로 변경해준다.

			for (int j = k - weight; j >= 0; j--) {
				dp[j + weight] = Math.max(dp[j + weight], dp[j] + val);
			}

코드로는 이렇게 되는데,

weight는 현재 넣을 물건의 무게, val은 물건의 가치이다.

j + weight가 항상 가능한 인덱스값을 갖게 하기 위해서 for문의 시작 범위를 k-weight부터로 해주었다.

 

그 물건만 넣었을 때의 값은 j=0일 때, dp[weight]값을 비교하게 되니 전 범위를 비교할 수 있게 된다.

 

여기서, 코드가 0부터 시작해도 똑같지 않냐고 생각할 수도 있는데, 그렇게 되면 위해서 말했던 "같은 물건을 또 넣지 않도록 해야한다" 는 점을 지키지 못해 문제가 발생한다.

현재 무게(j + weight)에서의 가치를 최대로 해야 하는데, 그걸 비교하기 위해서는 현재 무게보다 작은 무게에서의 가치들을 비교해야한다. 그런데 작은 무게부터 비교해주게 되면

최댓값으로 갱신된 가치가 다음 가치를 비교할 때 또 사용되게 된다. 그래서 인덱스를 가장 큰 것부터 사용해 준 것이다.

 

처음에 말했듯이, 이렇게 계산하게 되면

dp[i]는 무게 i까지 넣을 수 있는 물건의 가치합 중 최대 가치 합

즉, 최댓값을 따로 구할 필요 없이 배열의 맨 끝 값인 dp[k]가 최댓값이 된다.

배열 인덱스는 0부터가 아니라 1부터로 했는데, 무게랑 인덱스를 직접 매칭시켜서 비교해야 하기 때문에 이렇게 해야 훨씬 편함

 

시간복잡도

총 N개의 물건을 비교

버틸 수 있는 무게인 K까지 비교

시간복잡도: O(N*K)

N*K의 최댓값 = 100*100,000 = 10,000,000

시간제한은 2초이기 때문에 충분하다.

 

소스코드

import java.io.*;
import java.util.*;

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());
		// k무게에서의 최대 가치
		int[] dp = new int[k + 1];
		int[][] stuff = new int[n + 1][2]; // 0: 무게, 1: 가치
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			stuff[i][0] = Integer.parseInt(st.nextToken());
			stuff[i][1] = Integer.parseInt(st.nextToken());
		}

		// i로 돌리니까 자동으로 i번째 물건까지 고려한 것이 된
		for (int i = 1; i <= n; i++) {
			// i번째 물건까지 비교했을 때
			int weight = stuff[i][0];
			int val = stuff[i][1];

			// 추가로 넣는 경우부터 순서대로 고려
			// j==0일때는 해당 물건만 넣는 경우이다.
			for (int j = k - weight; j >= 0; j--) {
				dp[j + weight] = Math.max(dp[j + weight], dp[j] + val);
			}
		}
		System.out.println(dp[k]);
	}

}