2258번 정육점

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

처음 생각

문제에 의하면

1. 어떤 덩어리를 샀을 때, 추가 비용 없이 그 덩어리보다 가격이 싼 고기들은 얼마든지 덤으로 얻을 수 있음.

2. 원하는 양 또는 그 이상의 양을 구매하면 됨.

3. 무게가 문제의 핵심이 아님.

4. 최소 비용을 구하는 것이 문제.

→ 최소 비용을 구하는 것이므로

{가격, 무게} 가격 오름차순 ☞ 무게 오름차순으로 한 다음 

앞에서 순서대로 무게의 누적 합이 m보다 같거나 크게 되는 순간 그 때의 가격을 출력하도록 구현했었다.

하지만 답은 틀렸다.

두 번째 생각

문제에서의 

만약 가격이 더 싸다면 은혜가 필요한 양보다 더 많은 고기를 살 수도 있다.

라는 부분과 무게를 내림차순으로 해야 무게가 더 큰 것을 먼저 계산할 수 있고,

이때의 가격 또한 앞으로 진행을 덜 할 수도 있다.

즉, 무게가 더 큰 것을 먼저 계산할 수 있으니, 내가 첨부한 코드에서 temp가 m보다 더 빨리 크게될 수 있다.

가격 오름차순 ☞ 무게 내림차순으로 해봤지만 역시나 틀렸다.

(반례)

10 10

2 3

2 4

2 5

3 1

1 3

7 9

7 3

8 4

10 3

3 10

정답 : 3

오답 : 4

세 번째 생각

가격이 싼 것은 무료로 구입이 가능.

즉, 같은 가격들일 경우 돈을 추가로 합해야 했다.

그렇게 구현하니 런타임 에러가 떴는데, 정렬 방식에 문제가 있었다.

Integer.compare(a, b);을 많이 활용해야겠다.

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, m, answer = Integer.MAX_VALUE;
    static Vector<pair> v = new Vector<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()); // 무게
            int f = Integer.parseInt(st.nextToken()); // 가격
            v.add(new pair(f, s)); // {가격, 무게}
        }
    
        // 가격 오름차순 → 무게 내림차순
        Collections.sort(v, new Comparator<pair>() {
            public int compare(pair p1, pair p2) {
                if(p1.first < p2.first) {
                    return -1;
                }
                else if(p1.first == p2.first){
                    return -Integer.compare(p1.second, p2.second); // 내림차순
                }
                else {
                    return 1;
                }
            }
        });
        
        // temp : 무게의 누적 총 합을 구할 변수, same : 가격이 같을 때 가격의 누적 합
        int temp = 0, same = 0;
        boolean stop = false;
        
        for(int i=0; i<n; i++) {
            temp += v.get(i).second; // 무게 누적 총합 구하기
            if(i>=1 && v.get(i-1).first == v.get(i).first) {
                // 이전과 가격이 같을 때
                same += v.get(i).first; // 가격이 같은 것은 더해줌. v.get(i-1).first랑 같음.
            }
            else same = 0; // 가격이 다를 때
            
            // 조건 m보다 같거나 클 때
            if(temp >= m) {
                stop = true; // 표시
                answer = Math.min(answer, v.get(i).first + same); // 최소의 비용 계산
            }
        }
        
        if(stop) {
            bw.write(String.valueOf(answer) + "\n");
        }
        else {
            bw.write(String.valueOf(-1) + "\n");
        }
        
        bw.flush();
        bw.close();
    }
}
 
class pair{
    int first, second;
    pair(int f, int s) {
        this.first = f;
        this.second = s;
    }
}