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

 

2258번: 정육점

첫째 줄에 두 정수 N(1≤N≤100,000), M(1≤M≤2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나타내는

www.acmicpc.net

백준 사이트에서 풀 수 있는 정육점 문제입니다.

카테고리는 Greedy입니다.

 

19일 전에 처음 시도했던 이 문제를 중간에 과제 기간이라 하여 일주일 쉬긴 했지만 3주만에 드디어 풀었습니다.

 

풀면서 제가 막히거나 신경 쓴 부분은 다음과 같습니다.

1. 가격이 더 싼 고기를 무료로 얻을 수 있으므로 가격을 오른차순으롱 먼저 정렬하고,
무게를 빠르게 채워야 하므로 가격이 동일 한 경우 무게를 내림차순으로 정렬한다.

 

2. 가격이 더 싼 고기를 무료로 얻는다고 했지 가격이 같은 고기를 무료로 얻는다고는 안했다.

동일한 가격에 대해 누적된 가격을 계산해야 한다.

 

3. 2의 과정이 무게가 목표치보다 낮을 경우와 높을 경우에 필요한 연산이 다르다.

목표치보다 낮으면 항상 가격이 누적되고, 변동된 가격이 들어오더라도 이전 가격을 무시하면 된다.

반대로 목표치보다 높으면 가격을 더이상 누적하지 않고, 현재 최소 가격과 현재 가격만을 비교한다.

 

4. 모든 고기의 무게와 가격의 각 합인 unsigned int의 최대 값보다 작거나 같다.

때문에 조건에 부합하지 못해 -1을 출력해야 할 때 단순한 삼항연산자 등을 이용하면 <2^32 - 1>이 출력된다.
번거롭더라도 if문을 사용하거나, 출력 전에 string으로 형변환을 하는 등의 작업을 선행하자.

 

매우 간단하고, 처음에도 간단하다고 생각 했는데 3번 부분을 항상 놓치거나 잘못 작성하여 정답을 맞추지 못했다.

그리고 여태까지 문제를 풀면서 몇몇 문제는 정답 코드를 참조하기도 했는데,
이 문제는 정답률이 낮아서인지 마땅한 코드가 거의 없다.

아니, 그냥 검색 결과가 2개 정도 밖에 없다.

 

그래서 일부로 글 앞에 검색에 걸릴만한 내용을 추가하고, 하단에 코드를 작성했다.

이 문제에 막혀 참고를 하고자 하시는 분들은 다음 코드를 참고하시면 될 것 같다.

더보기
#include <iostream>
#include <vector>
#include <algorithm>

struct chunk {
	unsigned int weight;
	unsigned int price;
};

using namespace std;

int main()
{
	unsigned int length = 0, needs = 0, weight = 0, price = 0, before = -1;
	vector<struct chunk> meatlist;

	cin >> length >> needs;
	for (int i = 0; i < length; ++i)
	{
		cin >> weight >> price;
		meatlist.push_back(chunk{ weight, price });
	}

	sort(meatlist.begin(), meatlist.end(), [](const auto& a, const auto& b) { return ((a.price < b.price) || (a.price == b.price) && (a.weight > b.weight)); });

	weight = price = 0;

	for (const auto& iter : meatlist)
	{
		if (weight < needs)
		{
			if (before == iter.price)
			{
				price += iter.price;
			}
			else
			{
				before = price = iter.price;
			}
		}
		else
		{
			if ((before != iter.price) && (price >= iter.price))
			{
				before = price = iter.price;
			}
		}
		weight += iter.weight;
	}

	if (weight < needs)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << price << endl;
	}

	return 0;
}

 

혹 몇가지 testcase가 필요하신 분들은 아래 파일에 있는 것을 참고하시길.

유의미 하지는 않지만 그래도 없는 것 보다는 나을 것이다.

 

정육점 input.xlsx
0.01MB

+ Recent posts