[platinum2] [해설안봄,분류확인] 5896 효율적으로 소사기(체감 난이도 다이아급..)

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

 

티어에 비해 너무나도 어렵게 풀었던 문제였다... 체감상 플레1~다이아5 사이 정도 되었다.. 다이아5 그리디문제보다 어떤면에선(끝없는 논리의 늪...)힘들었다

 

처음 딱 보고 비용내에 쿠폰을 모두 쓸 수 있으면 쓰고, 쿠폰가격 오름차순 정렬로 골라가는건 생각하지 어렵지 않다. 

그 후의 과정이 생각하기 어렵다

 

우선 처음 생각한 방법은 

쿠폰 쓴 가격에 대한 오름차순, 원래 가격에 대한 오름차순 리스트를 둔다.

쿠폰을 K개쓰고 남은 돈은 쿠폰을 안쓴 리스트에서 비용이 낮은 것부터 가져온다.  여기서 중요한 점은 쿠폰을 이미 쓴 소는 쿠폰x리스트에서 제외하는 것이다.  그러나 이방법은 소를 살 수 있는 가장 효율적인 방법은 아니다.  

쿠폰으로 산 소들 중에, 쿠폰을 안썼을 때와 가격차이가 얼마 안나는 소는 쿠폰을 안쓰고, K + 1번째 소에 쿠폰을 먹여 사는것이 더 효율적일 수도 있기 때문이다.

그 후, 쿠폰리스트에서 K+1번째 소를 추가한다.  쿠폰은 K개만 있으므로 쿠폰리스트에서 소 한마리는 떨어져 나가야 한다.

여기서 나가야 할 소는 쿠폰을 안써도 손해를 가장 덜보는, (쿠폰x가격 - 쿠폰가격 이 제일 작은) 소를 내보내는게 맞다.

쿠폰리스에서 소 한마리가 쿠폰x리스트로 옮겨졌으므로, 쿠폰x 리스트는 새로 업데이트 시킨다. 

그렇게 쿠폰리스트에서 K + 2, K + 3... 번째 소를 추가하면서 손해를 가장 덜보는 소를 쿠폰x 리스트로 보내고, 쿠폰x리스트를 업데이트 해나가는게 처음 생각한 방법이었다.

그러나 이 방법에서 간과한 점이 있었다. K + 1, K + 2... 번째 소를 추가하다가, 추가한 소가 쿠폰x리스트에 들어있었을 때는 이 녀석을 쿠폰리스트로 옮길지 그냥 둘지를 생각을 못했다.    답은 간단하게, 쿠폰x 리스트에 들어갈 만큼   쿠폰x,쿠폰 가격차이가 적다면 그대로 두고, 아니라면 쿠폰리스트로 옮긴다는 것이었다.

 또 한가지 간과한 점은, 초기에 쿠폰리스트에 K개의 소를 두고,

나머지 소들 중 쿠폰x리스트에 둘 예정인 소들도  쿠폰x,쿠폰 가격차이를 비교해 쿠폰리스트로 옮길지 말지 정해야 한다는 것이다. (이 점을 생각하지 못해 한참 해맸다..;)

 

K개의 소를  쿠폰으로 사고, 나머지 소들은 쿠폰을 적용안했을 때 가격순으로 추가하면서,  가격차이가 크다면 쿠폰리스트로 옮기고, 쿠폰리스트에 있는 소중 가격차이 가장 적은 소를 쿠폰x리스트로 옮겨가면서  두 리스트를 업데이트 하면 된다.

 

 

그 후 쿠폰리스트에 소를 새로 추가하면서, 쿠폰x리스트 또한 업데이트 하면 된다.

 

그러나 이방법은 논리적으로 맞기는 하지만 쿠폰x리스트에 수시로 소가 들어갔다 나오며 정렬을 유지하려면 시간비용이 꽤나 크게 들 것이다.  또한 누적합을 이용해 최대한 살 수 있는 소의 마리수 까지 관리해야 하니 구현이 쉽지 않다.

 

그래서 다른 방법을 생각해 보았다.

쿠폰리스트에 소를 한마리 추가하면,  가격차이가 가장 적은 소를 쿠폰x리스트로 이동시키는 건 당연하다. 그런데 굳이 쿠폰x리스트를 관리하지 않고도, 단순히 가격차이만큼 비용이 늘어나고, 쿠폰리스트에 소 한마리가 추가된다는 것만 알아도 소의 현재 마리수와 전체 비용을 알 수 있다.

 

또한 쿠폰x리스트에 소를 추가 할 경우에는 전체비용은 단순히 추가된 소 만큼 증가할 것이다.

 

이 두 가지 경우를 설명한 이유를 설명하기에 앞서, 중요한 사실을 알아야 한다.

이 문제의 핵심은 쿠폰리스트, 쿠폰x리스트의 소들을 가격 오름차순으로 나열하고 쿠폰리스트에서 X개, 쿠폰x리스트에서 Y개를 가격순으로 가져오는 것이다.  X + Y = N 이고,   X와 Y의 값을 조정해 소의 최댓값을 구해야 한다.  유의해야 할점은 가격순으로 연속적으로 가져와야지 절대로 띄엄띄엄 가져와선 안된다는 것이다.

 

 

이 설명을 한 이유는 위의 그림에서 그리디하게 빨간 부분 (쿠폰리스트에 소 추가) , 파란 부분(쿠폰x리스트에 소 추가) 를 비교하며 둘 중에 전체비용이 적게 증가하는 경우를 선택해   나간다는 아이디어를 설명하기 위해서이다. 

여기서 켕기는 부분이 있다.  만약 쿠폰x리스트에 소를 추가했는데, 이 소가 쿠폰적용했을 때 가격차이가 커서 쿠폰리스트로 가야한다면 어떡할 것인가.

 

 

위와 같이 쿠폰x리스트에 소를 추가했는데 쿠폰 리스트로 가게 된다면, 쿠폰x리스트에 추가한 의미가 없을 것이다. 

그러나 이와같은 일은 일어나지 않는다. 파란색 소가 그림과 같이 쿠폰리스트로 간다고 했을 때, 그 사이의 소는(초록색) 쿠폰 먹였을 때는 파란색 소보다 작고, 쿠폰 안먹였을 때는 파란색보다 크다.  즉 초록색 소들은 무조건 파란색소보다 가격차이가 크다, 

따라서 파란색소가 가격차이가 커서 쿠폰리스트로 가야한다면, 초록색 소들도 무조건 쿠폰리스트로 가야 한다.  

그렇다면 파란색소를 쿠폰리스트에 추가할 바에, 초록색 소들을 선택하는게 더 효율적일 것이다. (당연히 쿠폰먹였을 때 가격이 더 싸므로) .  그런데 초록색 소 중에 가장 싼 소인 1번 소가 무엇일까? 바로  빨간색 소이다! 

쿠폰x리스트에서 파란색 소를 추가하려 하는데 쿠폰리스트로 가야 한다면, 그 경우보다 효율적인 경우가 빨간색인 경우이므로 무조건 빨간색 소를 추가하게 될 것이다.  

 

 

 

만약 반대의 경우는 어떨까

쿠폰 리스트에 소를 추가하려 하는데 소가 가격차이가 적어 쿠폰x리스트로 가야 하는경우를 생각해보자. 여기서 초록색 소는 빨간소보다 쿠폰 가격이 비싸고 쿠폰x가격은 더 싸다.  따라서 초록색 소가 빨간색 소보다 반드시 가격차이가 적다. 따라서 빨간색 소가 쿠폰x리스트로 이동해야 한다면 초록색 소들도 가야 한다. 그런데 기왕 쿠폰x리스트로 갈거면 빨간색 소보다 초록색 1번 소가 가는게 더 효율적이고,  초록1번 소는 바로 파란색 소이다.

 

따라서 어떤 경우이든 빨간색소, 파란색소를 비교하는 과정에서 다 해결이 되므로 걱정하지 않아도 된다.

이렇게 보면 심플하게 생각하면 구현은 쉽게 할 수 있지만... 처음에 복잡하게 오만가지 생각하다 보니 끊임없는 논리의 늪에 빠져들어 너무 힘들게 풀었던 문제였다, 나한텐 플레티넘 문제는 다 까다롭지만 특히나 티어에 비해 훨씬 힘들었던 문제였다.