Problem Solving/Baekjoon

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

jihyeon99 2024. 6. 26. 17:11

문제 정보

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

 

문제

 

문제 해결 과정

완전 탐색 풀이

서로 다른 N개의 물품품으로 배낭을 채울 수 있는 경우의 수는 다음과 같다.

물품 1(사용/미사용 → 2개) x 물품 2(사용/미사용 → 2개) x ... x 동전 N(사용/미사용 → 2개) = 2^N개

 

문제 조건에서 N이 최대 100이라고 하였으므로, 2^100 ≒ 10^30이므로, 문제 제한인 2초를 많이 초과한다. 따라서, 서로 다른 N개의 물품으로 배낭을 채울 수 있는 모든 경우의 수에 대해 이 무게가 K를 넘는지 확인하는 방식은 적합하지 않다.

 

DP 풀이

우선 그리디 풀이(가치 큰 것부터, 무게 작은 것부터, 단위무게당 가치 큰 것부터)를 생각했지만, 무게가 무겁다고해서 가치가 큰 것은 아니었다. 즉, 무게와 가치가 랜덤하게 주어졌으므로 그리디 풀이는 적절하지 않았다.

조건이 랜덤하게 주어져서, 완전 탐색을 해야하지만 시간 복잡도에 막힌다면..? dp 문제가 아닐까 생각하였다.

1번째 물품(w1=6, v1=13), 2번째 물품(w2=4, v2=8), 3번째 물품(w3=3, v3=6)이 있다고 했을때, 무게가 7인 배낭을 채우는 최대 가치는?

f(K)를 무게가 K일 때 최대 가치라고 하자.

1) 1번째 물품만 고려
f(7) = 13

2) 1번째 & 2번째(w2=4, v2=8) 물품 고려
2번째 물품 사용 x  →  f(7) : 1번째 물품으로만 
2번째 물품 사용 o  →  f(7-4) + v2 = f(3) + v2 : 1번째 물품으로만
→  1번째만을 사용할 때 항상 f(K)는 같은 값 나오므로 멱등성 보장 

3) 1번째 & 2번째 & 3번째(w3=3, v3 = 6) 물품 고려
3번째 물품 사용 x  →  f(7) = f(7) : 1번째 & 2번째 물품으로만
3번째 물품 사용 o  →  f(7-3) + v3 = f(4) + v3 : 1번째 & 2번째 물품으로만
→  1번째, 2번째만을 사용할 때 항상 f(K)는 같은 값 나오므로 멱등성 보장 

무게와 몇 번째 물품까지를 고려하는지가 배낭을 채우는 최대 가치에 영향을 준다. 그렇다면 최대 가치에 대해 멱등성(≒ Input이 같으면 Output이 같음)에 영향을 주는 요소가 2개이므로 dp가 2차원일 것이라고 생각하였고, 다음과 같이 정의하였다.

DP[i][j]를 1, 2, ... i번째까지 물품을 고려했을 때, 무게가 j인 배낭을 채우는 최대 가치
설명 무게 0 무게 1 무게 2 ... 무게 K
아무 물품 고려 x DP[0][0] DP[0][1] DP[0][2] ... DP[0][K]
1번째 물품 고려 DP[1][0] DP[1][1] DP[1][2] ... DP[1][K]
1~2번째 물품 고려 DP[2][0] DP[2][1] DP[2][2] ... DP[2][K]
...
1~n번째 물품 고려 DP[N][0] DP[N][1] DP[N][2]   DP[N][K]

 

이전까지 물품을 고려한 경우에 현재 새로운 물품을 추가로 고려했을 때의 최대 가치를 구하면 된다.

또한 현재 새로운 물품을 추가로 고려했을 때는 해당 물품을 배낭에 넣는 경우, 배낭에 넣지 않는 경우가 있을 수 있다. 이 중에 가치합이 더 큰 것을 택하면 된다.

DP[x][j] = Max(DP[x-1][j],  DP[x][j-현재 물품의 무게] + v( 현재 물품의 가치))
여기서, DP[x-1][j]는 추가된 물품을 넣지 x, DP[x][j-현재 물품의 무게] + v(현재 물품의 가치)는 추가된 물품을 사용 o

 

DP 풀이의 시간복잡도

위의 2차원 배열을 채워나가는 시간이므로(좌 → 우, 상  하 로 채워짐), 대략 N * K = (10^2) * (10^5) = 10^7이므로, 문제 제한인 2초에 충분하다.

 

DP 풀이의 공간복잡도

int로 2차원 배열을 만든다면, 대략 N * K * 4B = (10^2) * (10^5) * 4B = (10^7) * 4B = 40MB이다. 이는 문제 제한인 512MB에 충분하다.

 

코드

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[][] dp = new int[n+1][k+1]; // dp[i][j] : i번째 물건까지를 고려했을 때, 무게가 j인 배낭을 채우는 물건들의 가치합의 최대
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(st.nextToken()); // 현재 물품의 무게
			int v = Integer.parseInt(st.nextToken()); // 현재 물품의 가치
			
			for(int j=1; j<=k; j++) {
				// 1) 현재 물품을 배낭에 넣지 않는 경우
				int case1 = dp[i-1][j];
				
				// 2) 현재 물품을 배낭에 넣는 경우
				int case2 = case1;
				if(j-w >= 0) { // (배낭 무게 - 현재 물품 무게) >= 0이면, 현재 물품을 넣을 수 있는 가능성 있음
					case2 = dp[i-1][j-w] + v;					
				}
				
				dp[i][j] = Math.max(case1, case2); // 물품을 넣지 않는 경우과 물품을 넣는 경우 중 가치합이 더 큰 것
			}			
		}
		
		System.out.println(dp[n][k]);
		
	}
}