https://www.acmicpc.net/problem/2258
문제
> 은혜는 정육점에서 고기를 사려고 한다.
> 보통 정육점에서는 자신이 원하는 양을 이야기하면 그 양만큼의 고기를 팔지만,
은혜가 방문한 정육점에서는 세일 행사를 하고 있었기 때문에 N 덩어리의 고기를 이미 잘라놓고 판매하고 있었다.
> 각각의 덩어리들은 이미 정해져 있는 무게와 가격이 있는데,
어떤 덩어리를 샀을 때에는 그 덩어리보다 싼 고기들은 얼마든지 덤으로 얻을 수 있다
(추가 비용의 지불 없이).
> 또한 각각의 고기들은 부위가 다를 수 있기 때문에 비용과 무게와의 관계가 서로 비례하는 관계가 아닐 수도 있다.
> 은혜는 이러한 점을 고려하지 않고, 어느 부위든지 자신이 원하는 양만 구매하면 되는 것으로 가정한다.
> 또한 만약 가격이 더 싸다면 은혜가 필요한 양보다 더 많은 고기를 살 수도 있다.
> 각 덩어리에 대한 정보가 주어졌을 때, 은혜가 원하는 양의 고기를 구매하기 위해 필요한 최소 비용을 계산하는 프로그램을 작성하시오.접근
어떤 비용의 고기를 샀을 때, 그 고기보다 싼 고기들은 묻지도 따지지도 않고 덤으로 준다.
따라서 내가 무게 3에 비용 5짜리를 사면 이 고기보다 싼 (1, 2), (10, 3), (2,4) 등 전부 덤으로 받는다.
하지만 가격이 동일한 고기는 덤으로 받을 수 없다. 따라서 가격이 동일한 고기는 추가 구매를 해야한다.
이에 따라 동일한 비용의 고기가 여러개 있다면 최대한 무게를 많이 받을 수 있는 방법은
동일한 비용의 고기들 중 가장 무게가 많이 나가는 고기를 사는것이다.
예를 들어 고기 종류가 아래처럼 있다고 해보자.
1 2
2 3
4 1
2 5
3 5
5 5
이 때, 비용 5짜리 고기를 산다고하면 각각 1+2+4+2, 1+2+4+3, 1+2+4+5로 동일한 비용인데 9, 10, 12무게의 고기를 얻게 된다.
이제 12짜리 무게로 원한는 M 무게에 도달하지 못했다면 12 5인 상황에서 추가로 2 5나 3 5를 구매해서 무게를 맞춰야한다.
우린 항상 같은 비용일 때, 최고의 선택을 즉, 무게를 가장 크게 해야하므로 동일한 비용의 고기들은 항상 젤 무거운 고기부터 내림차순으로 골라야 최고의 선택이 보장된다.
따라서 12 5에 추가구매 하면 15 10, 17 15가 된다.
문제해결
> N과 M으로 고기의 수와 원하는 무게를 입력받아준다.
> 최종 구매 비용을 반환할 rst 변수에 초기값으로 Long의 최대값으로 최악의 경우를 준다.
> 고기의 정보와, 각 고기를 샀을 때의 최종으로 가지게 되는 무게, 비용을 저장할 meat, sum List배열을 선언한다.
> 고기의 정보를 입력받고 정렬하는데 기본적으로 비용에 대해 오름차순으로 정렬한다.
> 비용이 같은 고기들은 내림차순으로 정렬해서 동일 비용일 때, 최대의 무게를 가질 수 있도록 해준다.
> 누적합을 사용해 구매한 고기의 정보를 sum에 처리하는데 초기값으로 meat 배열에 첫 인덱스의 고기 정보를 가진다.
> 이 고기는 구매해도 덤으로 받는 고기들이 없으므로 초기값으로 적절하다.
> 그리고 다음 고기의 비용이 같을 때, 덤 없이 추가 비용을 지불하므로 이를 위해 prev로 직전 고기의 비용을 잡아두고 비교한다.
> 반복으로 모든 고기를 돌며보는데 top에 가장 최근 누적합, 직전까지의 고기들의 무게의 합과 비용을 가져온다.
> cur로 현재 고기의 무게와 비용 정보를 가져온다.
> 이제 가져온cur이 prev에 있는 고기의 비용과 다르면 직전의 sum을 덤으로 받을 수 있기 때문에 sum의 무게에 현재 고기의 무게를 더해주고, 비용은 현재 고기의 비용으로 처리해 sum에 추가해준다.
> cur과 prev가 같다면 동일 비용고기이므로 직전까지의 sum을 덤으로 받을 수 없기 때문에 무게를 누적하고 비용도 현재 비용으로 교체가 아닌 누적을 해준다.
> 위 과정이 끝나면 sum에 들어있는 모든 누적합 정보를 보며 원하는 무게 M이상인 sum 정보를 본다.
> 각각의 비용을 rst와 min연산을 통해 목표를 만족하는 경우 중 최소의 비용을 찾는다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//2258 정육점
static int N, M;
static long rst = Long.MAX_VALUE;
static List<long[]> meat, sum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
meat = new ArrayList<>();
sum = new ArrayList<>();
while(N-->0) {
st = new StringTokenizer(br.readLine());
meat.add(new long[]{Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken())});
}
meat.sort((a, b) -> {
int cmp = Long.compare(a[1], b[1]);
if(cmp == 0) return Long.compare(b[0], a[0]); // 비용 같으면 무게 내림차순
return cmp;
});
sum.add(new long[]{meat.get(0)[0], meat.get(0)[1]});
long prev = meat.get(0)[1];
for(int i = 1; i < meat.size(); i++) {
long[] top = sum.get(i-1), cur = meat.get(i);
if(cur[1] != prev){
sum.add(new long[]{top[0] + cur[0], cur[1]});
prev = cur[1];
}
else sum.add(new long[]{top[0] + cur[0], top[1]+ cur[1]});
}
for(long[] i : sum) if(i[0] >= M) rst = Math.min(rst, i[1]);
System.out.println(rst == Long.MAX_VALUE ? -1 : rst);
}
}
후기
문제가 너무 모호했다고 생각한다. 문제의 토시하나에 따라 처리가 달라졌다고 생각한다. 동일 비용 고기의 처리가 애매해서 고생했다.
