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

문제

 

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

 

2258번: 정육점

 

문제반례

다음은 반례로 나오기 좋은 것들을 모아놓은 것이다.

10 14
2 3
2 4
2 5
3 1
1 3
7 9
7 3
8 4
10 3
3 10

답 : 4

3 2
1 1
1 1
2 3

답 : 2

10 10
2 3
2 4
2 5
3 1
1 3
7 9
7 3
8 4
10 3
3 10

답 : 3

4 9
1 2
2 4
3 6
4 8

답 : 8

 

7 15

2 3

3 6

5 1

6 1

4 8

1 2

3 2

 

답 : 3

 

문제이해

 

 

• 첫째 줄에 덩어리의 개수(N)와 은혜가 필요한 고기의 양(M)을 입력합니다.
• 덩어리들의 무게(W)와 가격(V)을 N개의 줄 만큼 입력합니다.
• 필요한 양의 고기를 구매하기 위해 필요한 최소 비용을 출력하고 만약 최소 비용을 구하지 못하는 경우 -1을 출력합니다.

 

이 문제에서 주의 깊게 봐야 할 특징은 바로 '어떤 덩어리를 샀을 때에는 그 덩어리보다 싼 고기들은 얼마든지 덤으로 얻을 수 있다(추가 비용의 지불 없이).'와 '비용과 무게와의 관계가 서로 비례하는 관계가 아닐 수도 있다.'이다.

 

만약 가격이 V인 고기를 구매한다고 하면 가격이 (V - 1 ~ 1)인 고기들은 구매 비용을 지불하지 않고 구매할 수 있다는 것이다.

또한, 고기의 무게가 고기의 비용과 관련이 있지 않기 때문에 최소 비용을 지불하기 위해서는 우선 배열을 가격에 대해서 오름차순으로 정렬하여야 하고 가격이 같은 고기가 있을 경우 고기의 무게에 대해서 내림차순으로 정렬해야 한다.

 

이후 배열의 첫번째 인덱스부터 시작하여 고기의 무게를 계속 더해간다. 구매하고자 했던 고기의 양보다 구매한 고기의 무게가 크거나 같은 경우부터 시작하여 구매 비용이 최소가 되는 순간을 찾아야 한다.

 

예시를 들어 이해하기 쉽게 설명해 보겠다.

배열 인덱스	0	1	2	3	4	5	6
무게(g)	6	5	3	1	2	3	4
비용(원)	1	1	2	2	3	6	8

위는 N개의 고기가 정렬 규칙에 따라 미리 정렬된 경우를 표로 나타낸 것이다. 이때 은혜가 구매하고자 하는 고기의 양이 15원이라고 한다.

첫 번째 인덱스부터 무게를 합해나갈 경우 3번 인덱스에서 총 구매하게 될 고기의 양이 15g이 되게 된다. 이미 구매하고자 하는 양을 충족했지만 여기서 멈춰서는 안 된다. 구매하려는 고기의 양보다 구매할 고기의 양이 더 많아도 되고 현재의 경우 구매하기 위해서는 4원을 지불해야 되는데 만약 4번 인덱스의 고기까지 구매하게 된다면 3원만 지불하고 17g의 고기를 구매할 수 있기 때문이다.

 

위의 상황으로 봤을 때 최소 비용을 구하기 위해서는 필요한 고기의 양을 충족한 순간부터 모든 고기를 구매하는 경우까지 중에 가격이 최소가 되는 경우를 찾아야 한다는 것을 알 수 있다. 코드로 구현하면 다음과 같다.

 

문제해결

 

#include<queue>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<pair<int, int>> meat;

bool sortM(const pair<int, int>& A, const pair<int, int>& B) {
	if (A.second != B.second) {
		return A.second < B.second;
	}
	else {
		return A.first > B.first;
	}
}

int maxP{ -1 };
int payP{ 0 };
int overP{ -1 };

void buyMeat(int idx, int sum, int M) {
	if (idx >= meat.size()) {
		if (sum < M) {
			cout << "-1";
			return;
		}
		else {
			cout << overP;
			return;
		}
	}
	sum = sum + meat[idx].first;
	if (meat[idx].second >= maxP) {
		if (meat[idx].second == maxP) {
			payP = payP + meat[idx].second;
		}
		else {
			maxP = meat[idx].second;
			payP = meat[idx].second;
		}
	}
	if (sum >= M) {
		if (overP == -1) {
			overP = payP;
		}
		else {
			if (overP > payP) {
				overP = payP;
			}
		}
	}
	buyMeat(idx + 1, sum, M);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, M;
	int W, V;
	cin >> N >> M;
	for (int i{ 0 }; i < N; i++) {
		cin >> W >> V;
		meat.push_back(make_pair(W, V));
	}
	sort(meat.begin(), meat.end(), sortM);
	buyMeat(0, 0, M);
}

 

bool sortM

정렬 규칙에 따라 vector <pair <int, int>> meat를 정렬하기 위해 만든 함수이다. 이를 통해 meat를 정렬 규칙에 따라 정렬하였다.

 

void buyMeat

재귀함수를 통해 최소 비용을 구했고 overP는 구매한 고기의 양이 구매하고자 하는 고기의 양을 넘긴 이후부터 고기를 전부 구매할 때 까지중 구매 비용이 최소가 되는 경우를 저장하는 데 사용하였다. 문제에서도 언급되었지만 구매하는 고기보다 가격이 작은 고기들만 구매비용을 지불하지 않고 구매할 수 있기 때문에 구매하는 고기와 가격이 같은 고기들은 구매비용을 지불하고 구매하였다.

 

int main

입력받아야 할 인수들을 입력받고 butMeat를 통해 구매하고자 하는 최소비용을 출력하였다.

 

문제후기

문제를 이해하고 나니 시간제한도 넉넉했고 구현하기도 어렵진 않아서 풀 수 있었다.