[diamond5][해설안봄,분류안봄]~ 16225 제271회 웰노운컵

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

 

지금 까지 풀어본 다이아 문제중 가장 수월하게 풀렸던 것 같다. 개인적인 체감난이도론 바로 전에 풀었던 플레2 그리디문제 '효율적으로 소사기'보다 쉬웠던 것 같다.

 

우선 보면 직감적으로 그리디 문제라는 감이 온다.  A가 2문제를 선택하면   B가 거기서 하나를 선택하는 것인데 가장 먼저 든 생각은 이렇다.  B의 입장에서 점수 내림차순으로 정렬한다. 그럼 여기서 가장 큰 점수는 B[0] 이고,  A가 B[0]을 선택하고 나머지 한가지는 어떤걸 선택하더라도 인공지능은 B[0]을 선택하게 될 것이다.

 

 

다음과 같은 상황에서 1번째와 4번째를 뽑으면 B는 무조건 첫번째를 가져가게 된다. 

 다음으론 2번째, 3 번째를 뽑게되면 아래와 같다

i가 작은 순으로 순차적으로 B가 가져가고 있는 상황이다.

그다음으론 B가 5번째를 가져가게 될 것이다.

이런 상황을 관찰해 보았더니, 중요한 사실을 발견했다. 모든 i에 대해 1 ~ i번째까지 구간에서 B의 선택 횟수는 A의 선택 횟수 이상이다. 

 10C2, 즉 10개중에 2개를 선택하는 모든 상황에서 B선택(파란색)은 A선택(빨간색)보다 왼쪽걸 선택하므로, 어떻게 선택하든지 간에 모든 구간에서 파란색은 빨간색 갯수보다 많거나 같아야 한다.

 

 

잉점을 상기해두고, 어떻게 하면 A가 선택하는 값들의 합이 최대가 될지 생각해보자.  

우선 당연히 1번째값은 B가 차지하게 된다. 그러므로 1~1 구간에서는 반드시 파란색이 차지하게 된다. 방금전 규칙에서   

 

1~2번째 구간에선 다음과 같이 파란색이 1~2개를 모두 차지하게 될 수도 있다.

 

그러나 우리는 그리디하게1~2 구간에서 A가 얻을 수 있는 최대점수합을 구한다고 해보자. 그렇다면 아까의 규칙에 대해 빨간색(A선택) 갯수는 파란색 이하여야 하므로 최대 한개 까지 가능. ) 1~1구간에서 이미 파란색이 고정이므로 빨간색을 선택하려면 2번째를 선택해야 한다.

이제 3번째의 경우를 보면 파란색 2개, 빨간색 1개가 되어야 한다. (아까 규칙대로 파란색 갯수가 빨간색갯수 이상이여야 함). 그렇다면 3번째를 파란색으로 선택하면 될까? 그러기엔 A[i]를 보면 A[3] > A[2] 이므로 이대로 3번째를 B에게 넘기기는 아깝다. 그런데 1~3 구간에서 빨간색이 한개이기만 하면 되므로, 2번째를 파란색으로 만들고 3번째가 빨간색을 차지하는것이 가능하다.   

 

4번째를 보면 지금까지 파랑2개 빨강1개였으므로 4번째는 굳이 비교하지 않고도 빨간색으로 선택이 가능하다.

 

5번째에서는 4번째와 달리 빨간색 갯수때문에 빨간색 갯수를 한개 더 늘리는 것이 불가능하다.  그런데 지금까지 선택한 빨간색은 3,4번째 인데, 이중에 가장 작은 값은 A[4]=3이다.  A[5] = 6 인데, 이런 경우  4번째를 B에게 넘기고 A가 5번째를 선택하게 만들 수 있다. 즉                 지금까지 선택한 빨간색중 가장 작은 A값 < A[i]  의 경우, 좌항을 B에게 줘버리고 i번째를 A것으로 선택할 수 있다. (그리디하다)

 

6번째는 파란색이 더 많은 상황(B가 더많이 선택한 상황) 이므로 비교없이 A가 선택하게 할 수 있다.

7번째도 아까와 마찬가지로 선택한 빨간색 중 최솟값이 A[6] = 2 , A[7] = 4 이므로, 6번째를 B에게 넘기고 7번째를 A가 가져올 수 있다. 

 

 

계속반복하다가 9번째에서는 기존 선택한 빨간색의 A최솟값이 A[8] = 1인데 A[9] < A[8] 이므로  이 경우 9번째는 그냥 B가 가지게 둬야 한다. (그리디하게)

 

최종적으론 다음과 같이 된다

 

 

이렇게 1~i번째 구간에 대해 이 구간에서 빨간색을 가능한 만큼 선택하게 하면서, ( i / 2개) 빨간갯수=파란색갯수 인경우 기존 선택한 A중 가장 작은 값이 A[i]보다 작다면 버리고, i번째를 A로 선택하게 만들면 된다.

 기존 선택한 A값은 우선순위 큐로 관리하면서 버려야 할 때 poll()하게 한다면 쉽게 관리할 수 있다.

구현은 다이아 치곤 굉장히 간단했고, 사실 이문제는 5896 효율적으로 소사기와 아예 다른  문제긴 하지만,  그 문제를 풀어 봤기 때문에 A 와 B 2가지가 있고, 그리디하며,  순차적으로 따져야 한다는 점에서  정렬 한후 우선순위큐로 두어야 한다는 아이디어를 어렵지 않게 생각할 수 있었던 것 같다.