jay153의 PS 일지
BOJ 23736 본문
https://www.acmicpc.net/problem/23736
코드
http://boj.kr/247a5b6a0d2141aeafb65039b92cac04
3rd UNIST Algorithm Programming Contest Uni-CODE 2021 G
난이도 : P2
Elapse time : 10min
우선 문제 상황이 꽤 복잡해 보였다. 문제를 간단화하기 위해 게임을 하면서 선택한 간선들을 초기 그래프에 표시했을 때 어떤 모양이 될지 생각해 보았다. 당연하게도 그래프의 스패닝 트리가 되는 것을 확인했고 Yunee가 어떻게 빨간색과 파란색을 나누든 최대 스패닝 트리를 고를 수 있다. 그렇다면 Woongbae의 입장에서는 최대 스패닝 트리를 만드는 것이 이득이고 반대로 어떻게 빨간색과 파란색을 나누든 Woongbae가 얻는 점수가 같다면 Yunee는 개수를 최대한 반에 가깝게 나눠 점수를 최대화하는 것이 이득이다. 이를 각각 계산하여 비교해 풀었다.