BOJ 백준 6066 Buying Hay

 

문제 : https://www.acmicpc.net/problem/6066

 

[ 문제 요약 ]

• 목표 건초더미 무게가 주어지고, 각 업체들의 개수가 주어집니다.
• 각 업체들에서 건초 더미를 무제한으로 가져올 수 있고, 업체들마다 건초더미의 무게당 가격이 주어집니다. 건초 더미는 나눌 수 없고 덩어리로 사야 됩니다.
• 이때, 목표 건초더미 무게(초과 상관없음)를 달성하기 위해 드는 최소 가격을 출력

 

[ 테스트 케이스 설명 ]

2 15// 업제개수(1<=100), 목표 건초무게(1<=50,000)
3 2	// 건초 무게(1<=5,000), 비용(1<=5,000)
5 3
//9 목표 건초무게를 달성할 최소 비용(무게는 초과달성 가능)

[ 반례 데이터 ]
3 25
10 2
10 3
10 2
//6

 

[ 문제 풀이 ]

한 업체의 건초 더미를 무제한으로 살 수 있으므로 무한 배낭 문제입니다.

 

그리고 건초 무게를 초과해서 달성해도 비용만 최소 면 상관없기 때문에

 

dp 식을 구할 때, 현재 for 문의 값으로 미래 무게를 구해야 합니다. 이 부분은 코드로 봐야 합니다.

 

dp 구조는 아래와 같습니다.

 

dp[무게] = 해당 무게까지 드는 비용의 최소

 

위와 같이 dp 안에 담긴 값 자체의 의미가 비용의 ‘최소’이기 때문에, dp 배열은 큰 값으로 초기화해주어야 합니다.

 

그래야 min 함수로 최소를 구할 수 있습니다.

 

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
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());// 업제개수(1<=100)
		int M = Integer.parseInt(st.nextToken());// 목표 건초무게(1<=50,000)
		int dp[] = new int[M + 1];	// 건초 더미 무게 마다 드는 최소 비용
		
		Arrays.fill(dp, 1<<30);
		
		dp[0] = 0;
		
		for(int i=1; i<=N; i++)
		{
			st = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(st.nextToken());// 건초 무게(1<=5,000)
			int c = Integer.parseInt(st.nextToken());// 비용(1<=5,000)
			
			for(int j=0; j<=M; j++)
			{
				int nextWeight = Math.min(j + w, M);
				
				dp[nextWeight] = Math.min(dp[nextWeight], dp[j] + c);
			}
				
		}
		System.out.print(dp[M]);
	}
}

 

[ 코드 해설 ]

• 먼저 dp 배열을 큰 값으로 초기화하고, dp[0] 값은 0으로 초기화하여, 논리적으로, 무게 0을 만들 때 드는 비용을 0으로 놓습니다.
• 안쪽 for 문의 j 값을 보면, 0 무게부터 M 무게까지 반복합니다. 현재 j 무게 일 때를 기준으로 nextWeight을 구합니다. 만약 nextWeight 무게가 M을 초과한 경우, M으로 맞춰 줍니다.
• 그리고 현재 무게(j)에서 비용(c)을 더한 값과, 지금까지 구한 dp[nextWeight] 값을 비교하여 작은 값으로 세팅해 줍니다.