백준 2258번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	골드 4

---

풀이

 이 문제를 풀면서 내가 자꾸 하는 실수를 되짚어보았다. 이 문제를 정리하면 임의의 고기의 가격 미만의 고기는 공짜로 얻을 수 있을 때, 원하는 고기의 양을 만들기 위한 최소비용을 구하는 문제이다. 구현에 문제는 거의 없었지만, 정말 많은 실수를 하면서 무수한 WA를 받았다... 변명이나 해보자면 전날 저녁도 제대로 못먹고, 3시간 반정도 자고 일어나자마자 문제를 풀고 있지만... 사실 지금까지 비슷한 실수(물론 이쯤되면 실수라고 하면 안될거 같다)를 여러번 해왔기 때문에 항상 주의해야할 것 같다.

 

 문제를 보자마자, "아 이거 정렬하고 무게 누적합해가면서 최소가격 찾으면 되겠구나" 라고 바로 러프하게 떠올랐고, 이를 실행에 옮겼다. 이제부터 내가 어떤 실수들을 겪었는지 그 과정을 살펴보자.

 

 우선, 문제 제대로 안읽고, 임의의 고기의 무게 미만인 다른 고기들을 공짜로 얻을 수 있다고 착각하여 구현에 실수를 했다. 열받는건 예제입력은 이렇게 해도 맞는다는 것이다. 차라리 틀렸으면 발견이라도 했겠는데 참...

 

 이 다음은 구매가 불가능한 경우 -1을 출력하는 것을 누락했다. 정확히는 이를 읽지 못했다. 이때문에 정답값을 저장할 변수의 값을 수정해야했다.

 

 이 다음에서야 내가 문제를 잘못 읽고, 무게 미만으로 비교하고 있다는 것을 깨달았고, 코드를 수정했다. 비용을 기준으로 정렬을 한 후, 무게를 누적합을 해가며 원하는 무게가 만들어질 때의 최소 비용을 구했다.

 

 마지막으로, 이 문제에는 중복 데이터가 존재할 수 있다. 무게가 같던, 비용이 같던, 아니면 둘 다 같던 어쨌든간에 중복 데이터는 얼마든지 존재할 수 있다. 왜냐하면 이 문제에서 중복은 없다고 한 적이 없으니 말이다. 문제에서 따로 언급이 없는 이상 중복을 항상 고려해야하는데, 이 부분도 자주 실수하는 것 같다. 무게만 같은건 상관이 없는데, 비용이 같으면 문제가 좀 생긴다. 해당 문제에서는 어떤 무게 미만의 고기만 공짜다. 만약 같은 가격의 고기가 여러개 있다면, 이들은 공짜로 받을 수 있는게 아니기 때문에 전부 가격을 지불해야한다. 이 부분을 구현해야했다.

 

 러프하게 떠올린 풀이는 앞에서 말한대로 "정렬하고 무게 누적합해가면서 최소가격 찾으면 되겠구나" 였었다. 계속되는 실수(?)를 통해 구체화한 최종적인 풀이는 이렇다.

• 비용을 기준으로 오름차순, 비용이 같은 경우 무게를 기준으로 내림차순 정렬을 한다. 비용이 같은 고기들이 있다면, 무게가 제일 많이 나가는 것부터 구매하여 최대한 적은 비용으로 무게를 채우기 위함이다.
• 선형 완탐을 통해 비용이 작은 고기들부터 무게를 누적합한다. 비용은 임시변수에 저장한다. 고기의 개수가 10만개밖에 안되고, 시간제한은 2초기 때문에 완전탐색을 해도 널널하다.
• 원하는 무게가 만들어졌다면, 비용을 비교한다. 
• 만약 지금 보고 있는 고기들의 가격이 같다면, 임시 변수에 비용을 계속 더한다.
• 최종적인 비용을 출력한다.

내가 실수하는, 아니 이제 실수라고 하기에도 뭐한, 내가 자주 놓치는 부분을 정리하면 다음과 같다.

• 문제 조건을 누락하거나, 착각하는 것
• 중복여부

계속 신경쓰면서 풀어야 할 것 같다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;

int n, m;
vector<pll> meat;

void input() {
	int a, b;
	cin >> n >> m;
	meat.resize(n);
	for(auto& [w, c] : meat) cin >> w >> c;
	sort(ALL(meat), [](const pll& a, const pll& b){
		if (a.second != b.second) return a.second < b.second;
		else return a.first > b.first; 
	});
}

void sol() {
	ll ans = __LONG_LONG_MAX__, tmp = meat[0].second;

	if (meat[0].first >= m) {
		ans = min(ans, meat[0].second);
	}
	else {
		for(int i = 1; i < n; i++) {
			if (meat[i].second != meat[i - 1].second) {
				tmp = meat[i].second;
			}
			else {
				tmp += meat[i].second;
			}

			meat[i].first += meat[i - 1].first;
			if (meat[i].first >= m) {
				ans = min(ans, tmp);
			}
		}
	}

	cout << (ans == __LONG_LONG_MAX__ ? -1 : ans);
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}