dk10211   3달 전

대략적인 알고리즘을 설명 드리자면 B가 가져갈 값은 내림차순 정렬(B기준)1~m*2(문제에선 k)중 값으로 한정되어 있으므로 

1~m*2범위 안에서는 플레이어  A가 이것을 가져간다면 B에게 그만큼 손해를 준다고 가정하여 A[i]+B[i]를 기준으로 내림차순 정렬을 하여 앞선 1~m개를 가져가게 하고 B가 가져갈 숙련도들은 k라는 우선순위 큐를 만들어서 따로 보관해 두었습니다. 그리고 m*2+1~n까지의 남은 숫자들은 비교를 하며 선택적으로 취하는데 이 선택의 기준은 a(자신이 포기하면 플레이어 B가 바로 가져갈 값들),b(자신이 포기해도 B가 가져가지 않을 값들)로 분류해서 최솟값을 찾고 그것을 최소이득이라 하였을 때 그 이득보다 선택하는 값이 크다면 넣는 식으로 코드를 짰습니다. 

혼자서 반례를 찾는 건 너무 힘들 것 같아 부탁 드려봅니다.

댓글을 작성하려면 로그인해야 합니다.