백준 2258번 정육점[C++]

1. 문제 풀이

 백준에 등록된 태그에는 그리디라고 나왔지만 저는 parametric search를 사용하여 풀이하였습니다. 고기를 특정 금액만큼 사기로 이분 탐색으로 결정합니다. 고기의 가격이 특정 금액보다 작거나 같은 경우를 찾아 mx에 저장합니다. mx와 비용이 같으며 아직 수중에 돈이 남아있는 경우 해당 고기를 사기로 결정하고, mx보다 작은 고기는 무게만 추가하는 로직을 추가하여 순회합니다. 이때, 구매하거나 덤으로 받은 고기들의 무게 총합이 M 이상인지 검사하면 됩니다.

2. 소요 시간 및 경과

• 시작 시간: 12시 08분
• #1 제출 시간: 12시 18분
  • 4% WA
  • 오버플로우인지 검사하기로 결정
• #2 제출 시간: 12시 20분
  • 4% WA
  • 오버플로우가 아님, 최대 금액과 같은 고기는 별도로 구매해야 된다는 사실을 인지
• #3 제출 시간: 12시 36분
  • 40% WA
  • 알고리즘 태그를 까보았더니 그리디여서 그리디 형식으로 코드 재작성하기로 함
• #4 제출 시간: 13시 07분
  • AC
  • 그리디 코드를 갈아엎고, 이분 탐색 코드에서 MX값을 int형 최댓값보다 크게 설정하였더니 AC

총 소요 시간: 59분

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

// startTime: 12:08

const ll MX = 0x7ffffffff;

int n, m;
vpi meat;

bool solve(ll cur) {
    bool flag{};
    ll tot{}, cost{cur}, mx{};
    for(auto &[c, w] : meat) {
        if(cur < c) continue;    
        if(!flag) {
            flag = 1;
            mx = c;
        }
        if(mx > c) {
            tot += w;
        }
        else if(mx == c && cost - c >= 0) {
            tot += w;
            cost -= c;
        } 
    }

    return tot >= m;
}

int main() {
    fastio(nullptr, false);

    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        int w, c;
        cin >> w >> c;
        meat.pb({c, w});
    }

    sort(rall(meat));

    ll st{}, en{MX};
    while(st + 1 < en) {
        ll md = (st + en) >> 1;
        (solve(md) ? en : st) = md;
    }

    cout << (en == MX ? -1 : en);
}

 

4. 제출 결과