[그리디 스터디] $A_i$ or $B_i$ 선택하기

* 논리적 오류등의 지적은 환영합니다.
* 스터디를 진행해주신 dk10211님께 감사드립니다.

 

수열 $A$, 수열 $B$에서 $x=i$일 때, $A_x$ 혹은 $B_x$중 하나만을 골라 정답 집합 $S$를 만든다고 할 때, $S$를 만들기 위한 최적해를 구하는 방법을 소개합니다.

 

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

17169번: Eat Economically

$1$부터 $2N$까지, 아침에 식사할 때의 비용과 저녁에 식사할 때의 비용이 주어지고, 모든 메뉴는 아침 혹은 저녁에만 먹어야 합니다. (즉, 아침에 $x$번 메뉴를 먹고 저녁에 $x$번 메뉴를 먹을 수는 없음)

먼저, 아침에 먹는 비용을 담은 배열을 $A$, 저녁에 먹는 비용을 담은 배열을 $B$라고 하고,
$A_i < A_{i+1}$, $B_i < B_{i+1}$이 되도록 정렬합시다. (우리는 최소한의 비용을 알고 싶기 때문에)

$AM$을 아침에 먹을때 드는 비용의 집합, $PM$을 저녁에 먹을때 드는 비용의 집합이라 합시다.

먼저 $AM$에 $A_i$를 넣는 비용 $cost_1$을 계산해봅시다. 
$cost_1 = A_i$

그 다음, 하나 더 고려해야할 사항이 있습니다. 
"$PM$에 있는 메뉴들 중, $AM$으로 옮기고, $B_i$를 $PM$에 넣었을 때, $cost_1$보다 더 이득인 경우가 있는가?"
$PM$에서 $AM$으로 옮기는 비용을 $C$라고 합시다.
이때 $C<0$이라면 $PM$ 에서 $AM$으로 옮길때 비용이 드는 것을 의미하고, $C \leq 0$이라면 비용이 절약됨을 의미합니다.

 

이를 수식으로 나타내면,
$cost_2 = B_i - C$가 됩니다.

이제 $cost_1$과 $cost_2$를 비교해서 더 작은것을 고르면, 현재 상황에서 이득을 볼 수 있는 선택이 됩니다.

하지만 위의 과정, $AM$에만 원소를 집어넣는 과정을 수행한다면 당연히 $A_i$와 $B_i$를 적절히 분배했을때의 최적해를 놓치는 경우가 생깁니다.

 

따라서 위의 과정을 $B_i$를 $PM$에 넣는 경우도 고려해 보아야 합니다.

 

먼저 $PM$에 $B_i$를 넣는 비용 $cost_1$을 계산해봅시다.
$cost_1 = B_i$

"$AM$에 있는 메뉴들 중, $PM$으로 옮기고, $A_i$를 $AM$에 넣었을 때, $cost_2$보다 더 이득인 경우가 있는가?"
$AM$에서 $PM$으로 옮기는 비용을 $C$라고 합시다.
(부호의 의미는 위에서 설명하였습니다.) 

이를 수식으로 나타내면,
$cost_2 = A_i - C$가 됩니다.

이제 $cost_1$, $cost_2$를 비교해서 더 작은것을 고르면 아까와 같이 현재 상황에서 이득을 볼 수 있는 선택이 됩니다.

이를 $N$번 반복하면 $2N = n(AM) + n(PM)$이 되도록 적절히 분배할 수 있습니다.

$C$를 계산하기 위해선 $A_i - B_k$ 혹은 $B_i - A_k$를 PQ에 저장하면 됩니다.

($A$, $B$를 정렬했으므로 $i$는 $k$가 아닐 수 있음을 주의해야 합니다.)

주의해야할 점은, 두 과정에서 $AM$ 혹은 $PM$이 비어있다면, $AM$ 혹은 $PM$에서 뽑아서 옮기는 과정이 불가능함을 base로 해야합니다. 

 

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

5896번: 효율적으로 소 사기

 

이 문제는 소 $N$마리 중, $M$원과 쿠폰 $K$개를 적절히 사용해서 최대한 많이 소를 구매하는 문제입니다.

 

먼저 쿠폰을 사용하지 않을 때의 가격을 정렬한 배열을 $A$ ($A_i < A_{i+1}$), 쿠폰을 사용했을 때의 가격을 정렬한 배열을 $B$ ($B_i < B_{i+1}$)로 정의하고,

쿠폰을 사용하지 않을 때의 비용의 집합을 $Q_n$이라고 하고, 쿠폰을 사용할 때의 비용의 집합을 $Q_c$라고 합시다.

 

앞에서 언급한 17169번과 비슷한 접근법으로 풀 수 있습니다만, 먼저 base가 필요합니다.

base > 쿠폰을 일단 다 써야합니다. ($A_i > B_i$ 이므로 쿠폰을 일단 다 사용해야 이득을 봄)

일단 쿠폰 $K$개를 다 써서 $Q_c$에 $B_i$를 저장합니다.

 

그 다음, 쿠폰을 다 사용했다면 이제 다음과 같은 결정을 내릴 수 있게 됩니다.

1 - $Q_n$에 쿠폰을 사용하지 않고 $A_i$를 넣는다.

2 - 이미 쿠폰을 사용한 소 중, $Q_c$에서 $Q_n$으로 옮기고 $Q_c$에 $B_i$를 넣는다. 

1번 경우에 비용은 다음과 같이 계산할 수 있습니다.

$cost_1 = A_i$

2번 경우에 비용은 다음과 같이 계산할 수 있습니다.

$cost_2 = B_i - C$
이때 $C$는 $Q_c$에서 $Q_n$으로 옮기는 비용을 의미하며, 음수일 경우에는 비용이 발생, $0$ 혹은 양수인 경우 비용이 절감됨을 의미합니다. 

 

따라서 $cost_1$과 $cost_2$를 비교하고, 비용이 적은 쪽을 선택하면 최적해를 구할 수 있습니다.