BOJ 16225 - 제271회 웰노운컵

 

아이디어만 있다면 풀 수 있다 이건가요?

 

---

내가 문제 2개를 고르면 상대가 가장 자신 있는 문제 하나를 가져간 후 내가 남은 문제를 가져간다.

'나'와 상대는 i 번째 문제에 대해 각각 Ai, Bi 만큼의 자신감 수치를 가지고 있다.

내가 문제 2개를 고르지만 정작 문제의 선택권은 상대에게 있다.

문제 2개를 적절하게 잘 고르면 최적의 상황을 얻을 수 있다는데.... 당장은 보이지 않는다.

우선 문제의 선택권이 상대에게 있다는 것에 초점을 두고 Bi를 기준으로 정렬을 해보자.

4 2 8 6
6 5 7 8

 

 

2 4 8 6
5 6 7 8

 

여기서 맨 뒤에 있는 문제는 무조건 상대가 가져가는 문제, 맨 앞의 문제는 무조건 내가 가져갈 수 있는 문제임을 알 수 있다.

그럼 어떤 식으로 두 개의 문제를 골라야 자신감 수치를 최대화할 수 있을까?

이제 우선순위 큐로 문제들을 관리해 주면 되는데 각 상황에서 문제를 두 개씩 선택해야 하므로 앞에서부터 두 개씩 우선순위 큐에 넣어준다.

이후 문제를 고르는 상황별에 따라 우선순위큐의 최솟값들의 합이 우리가 찾고자 하는 자신감의 최대이다.