BOJ 5896 : 효율적으로 소 사기

알고리즘 문제 전체 링크

 

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

 

 

우선순위 큐를 이용하여 문제를 풀 수 있다.

 

아래의 경우에 대해서 생각해보자.

 

1) 쿠폰을 사용할 수 없는 경우.

모든 소의 원가에 대해 가장 가격이 낮은 소부터 산다.

 

2) 모든 소에 대해 쿠폰을 사용할 수 있는 경우.

모든 소의 쿠폰 적용가에 대해 가장 가격이 낮은 소부터 산다.

 

두 경우는 쉽게 해결할 수 있다.

문제는 쿠폰의 수가 0 < K < N인 경우이다.

 

쿠폰을 사용하였을 때, 가격이 가장 작은 소부터 고르고, 남은 소 중에는 원가에서 가장 싼 가격만 고를 경우 

아래와 같은 문제가 생길 수 있다.

---

먼저 돈이 7원, 쿠폰은 1장만 쓸 수 있는 경우를 보자.

 

소1 : 원가 - 10원, 쿠폰가 - 5원

소2 : 원가 - 2원, 쿠폰가 - 1원

 

쿠폰을 사용하였을 때 소2가 가장 싸다.

그러면 소1 원가 10원 + 소2 쿠폰가 1원 = 11원으로, 소를 한 마리만 구매할 수밖에 없다.

 

그런데 할인율이 높은 소1에 쿠폰을 적용하면

소1 쿠폰가 5원 + 소2 원가 2원 = 7원으로 소 두 마리를 구매할 수 있다.

 

따라서 무작정 가격이 싼 경우만 사지말고,

기존에 사용한 쿠폰을 취소하고, 현재 선택한 소에 쿠폰을 적용하면 더 좋은 경우에 쿠폰을 교체한다.

 

즉, 쿠폰가가 더 싼 소가 있더라도,

다음에 사야할 소에 쿠폰을 사용하는 것이 더 괜찮은 할인율이라면 쿠폰을 교체한다.

 

아래와 같이 로직을 수정할 수 있다.

 

1) 모든 소의 쿠폰 적용가에 대해 가장 가격이 낮은 소부터 산다.

2) 쿠폰을 모두 사용한 경우, 쿠폰을 교체하는 것이 나은 선택인지 확인한다.

   2-1) 쿠폰을 교체하거나

   2-2) 원가 중 가장 싼 것을 산다.

 

위의 예시로는 소 2를 쿠폰가로 산다. 이때 원가 - 쿠폰가 = 1이 된다.

즉, 소 2는 쿠폰가로 샀을 때 1만큼 돈을 아낀 것이다.

이 쿠폰을 포기하고 다른 소(여기에서는 소1)를 산다면, 

소1의 가격은 소1의 쿠폰가 + (소2의 원가 - 쿠폰가)가 되는 것이다.

(쿠폰을 물렸으므로, 그 비용을 추가)

 

따라서 구매한 소의 (원가 - 쿠폰가)도 우선순위 큐에 저장한 후에

쿠폰을 교체하는 것이 나은지 비교하면 된다.

 

쿠폰을 교체할 때는 (원가 - 쿠폰가)가 가장 작은 것부터 교체해야 비용의 손실을 최소화한다.

따라서 (원가 - 쿠폰가)도 작은 값을 항상 기억해둔다.

---

위의 경우를 해결하기 위해 우선순위 큐를 3개 이용한다.

원가, 쿠폰, 그리고 원가 - 쿠폰의 차이에 대한 최소힙 3개가 필요하다.

 

가격의 범위가 크기 때문에, long long int로 선언한다.

typedef long long int ll;

int N, K;
ll M;

typedef struct st
{
	ll value;
	int idx;
}HEAP;

HEAP price[50500]; /* 원가 */
HEAP coupon[50500]; /* 쿠폰사용 시 가격 */
HEAP diff[50500]; /* 원가와 쿠폰의 차이 */
int phn, chn, dhn;

int check[50500]; /* 구매한 소와 쿠폰을 체크 */
ll priceList[50500];
ll couponList[50500];

원가의 소를 선택하거나 쿠폰을 사용한 소를 선택하거나 중복 선택해서는 안되므로

각 가격별 index도 HEAP 구조체에 기억해둔다.

 

최소힙의 구현은 아래와 같다.

value가 long long int이기 때문에, 최악의 값은 0x7fffffff00000000으로 넣어두었다.

HEAP pop(HEAP *heap, int& hn)
{
	HEAP ret, tmp;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--].value = 0x7fffffff00000000;

	for (int i = 1; i * 2 <= hn;)
	{
		if (heap[i * 2].value > heap[i].value && heap[i * 2 + 1].value > heap[i].value) break;
		else if (heap[i * 2].value < heap[i * 2 + 1].value)
		{
			tmp = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void push(HEAP *heap, int& hn, ll x, int index)
{
	HEAP tmp;

	heap[++hn].value = x;
	heap[hn].idx = index;

	for (int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2].value < heap[i].value) return;

		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

---

priceList와 couponList에는 순서대로 가격을 입력받고,

price와 coupon heap에 index와 함께 push한다.

scanf("%d %d %lld", &N, &K, &M);

dhn = K; /* 쿠폰 K개 까지는 diff가 0이 된다. */

for (int i = 0; i < N;i++)
{
	ll p, c;

	scanf("%lld %lld", &p, &c);

	priceList[i] = p;
	couponList[i] = c;

	push(price, phn, p, i);
	push(coupon, chn, c, i);
}

위의 코드에서 dhn (diff heap의 heap index)가 K로 초기화하는 것은

push(diff, dhn, 0, 0)을 K번 한 것과 같다. (diff heap에서는 index가 의미가 없다)

 

즉, 쿠폰 K개 까지는 원가와 쿠폰가의 차이는 0으로 보면 된다. 

---

이제 가지고 있는 돈 M이 소모될 때 까지 소를 구매해보자.

 

원가로 소를 구매한 경우, price heap에서는 소의 가격이 pop되겠지만, coupon에서는 빠지지 않았다.

그 반대의 경우도 마찬가지이다.

 

따라서 가장 우선순위가 높은 price와 coupon heap이 check에 표시되었다면 pop을 해서 제거한다. 

while (check[price[1].idx]) pop(price, phn);
while (check[coupon[1].idx]) pop(coupon, chn);

check[price[1].idx]가 1이란 것은 coupon을 이용해서 price[1].idx를 구매한 경우로 볼 수 있다.

 

선택된 소를 모두 pop하였으니 이제 남은 소를 선택해보자.

 

쿠폰이 아직 남아있다면 diff[1]은 항상 0이다.

따라서 coupon과 price중 작은 값은 항상 coupon가가 선택될 것이다.

M이 여전히 남아있다면, 비용으로 coupon[1]을 소모한다.

그리고 diff 배열을 pop한 후, 원가 - 쿠폰가를 push한다.

구매한 소는 check로 표시한다.

if (diff[1].value + coupon[1].value < price[1].value) 
{
	HEAP tmp = coupon[1];
	ll cost = diff[1].value + tmp.value;

	if (M < cost) break;

	M -= cost;
	pop(diff, dhn);
	push(diff, dhn, priceList[tmp.idx] - couponList[tmp.idx], 0);
	check[tmp.idx] = 1;
}
else
{
	...
}

위의 코드는 쿠폰이 남아있지 않은 경우도 마찬가지로 성립한다.

coupon이 남아있지 않지만, diff[1] + coupon[1] < price[1]이라면, 쿠폰을 교체하는 것이 이득이다.

따라서 이전 coupon에 대해 할인된 가격 diff와 coupon가격이 cost가 된다.

 

쿠폰을 교체해도 의미가 없다면 남은 소 중 원가가 가장 싼 소를 선택하면 된다.

if (diff[1].value + coupon[1].value < price[1].value) 
{
	...
}
else
{
	HEAP tmp = price[1];
	ll cost = tmp.value;

	if (M < cost) break;

	M -= cost;
	check[tmp.idx] = 1;
}

 

위 과정을 M > 0인 동안 계속 반복한다.

필요한 비용 cost가 M보다 큰 경우, 종료하면 된다.

M이 남아있다면 소를 구매하였으므로 ans를 1씩 증가한다.

while (M > 0)
{
	while (check[price[1].idx]) pop(price, phn);
	while (check[coupon[1].idx]) pop(coupon, chn);

	if (diff[1].value + coupon[1].value < price[1].value) { ... }
	else { ... }

	ans++;
}

 

하지만 가지고 있는 돈 M으로 모든 소를 다 사고도 돈이 남는 경우,

불필요한 push, pop 때문에 segment fault가 발생할 수 있다.

따라서 모든 소를 다 구매한 경우 (ans == N)에도 while문을 종료할 수 있도록 ans < N 조건을 추가한다.

while (M > 0 && ans < N)

 

최종 코드는 아래와 같다.

#include <stdio.h>

typedef long long int ll;

int N, K;
ll M;

typedef struct st
{
	ll value;
	int idx;
}HEAP;

HEAP price[50500]; /* 원가 */
HEAP coupon[50500]; /* 쿠폰사용 시 가격 */
HEAP diff[50500]; /* 원가와 쿠폰의 차이 */
int phn, chn, dhn;

int check[50500]; /* 구매한 소와 쿠폰을 체크 */
ll priceList[50500];
ll couponList[50500];

HEAP pop(HEAP *heap, int& hn)
{
	HEAP ret, tmp;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--].value = 0x7fffffff00000000;

	for (int i = 1; i * 2 <= hn;)
	{
		if (heap[i * 2].value > heap[i].value && heap[i * 2 + 1].value > heap[i].value) break;
		else if (heap[i * 2].value < heap[i * 2 + 1].value)
		{
			tmp = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void push(HEAP *heap, int& hn, ll x, int index)
{
	HEAP tmp;

	heap[++hn].value = x;
	heap[hn].idx = index;

	for (int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2].value < heap[i].value) return;

		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

int main()
{
	int ans;

	scanf("%d %d %lld", &N, &K, &M);

	dhn = K; /* 쿠폰 K개 까지는 diff가 0이 된다. */

	for (int i = 0; i < N;i++)
	{
		ll p, c;

		scanf("%lld %lld", &p, &c);

		priceList[i] = p;
		couponList[i] = c;

		push(price, phn, p, i);
		push(coupon, chn, c, i);
	}

	ans = 0;
	while (M > 0 && ans < N)
	{
		while (check[price[1].idx]) pop(price, phn);
		while (check[coupon[1].idx]) pop(coupon, chn);

		if (diff[1].value + coupon[1].value < price[1].value) 
		{
			HEAP tmp = coupon[1];
			ll cost = diff[1].value + tmp.value;

			if (M < cost) break;

			M -= cost;

			pop(diff, dhn);
			push(diff, dhn, priceList[tmp.idx] - couponList[tmp.idx], 0);
			check[tmp.idx] = 1;
		}
		else
		{
			HEAP tmp = price[1];
			ll cost = tmp.value;

			if (M < cost) break;

			M -= cost;

			check[tmp.idx] = 1;
		}

		ans++;
	}

	printf("%d\n", ans);

	return 0;
}