카드 게임의 규칙이 아래와 같이 주어져있고 상대는 자기 마음대로 카드를 바꿀 수 있는 능력, 자신은 상대가 낼 카드를 미리 알 수 있는 능력이 있을 때 자신이 카드를 어떻게 내야하는지 출력하는 문제입니다.
- 규칙
- N개의 빨간색 카드와 파란색 카드가 있으며, 1부터 N까지 적혀있다.
- 상대는 빨간색 카드를 M개 가져오며 자신은 그와 똑같은 숫자로 파란색 카드 M개를 가져온다.
- 서로 카드 1장을 뒤집어서 내며, 큰 수를 낸 쪽이 이긴다.
- 이 행동을 K번 반복하여 이긴 횟수가 많은 사람이 최종적으로 승리한다.
그리고 자신은 상대가 내는 숫자보다 큰 수 중 가장 작은 숫자가 적힌 카드를 낸다는 조건과 자신은 항상 카드를 낼 수 있다는 조건이 있습니다. 이를 푸는 방법으로 생각해보면 자신이 가진 숫자를 정렬한 후, 이분 탐색으로 자신이 내야 할 카드의 숫자를 찾고, 이미 낸 카드라면 그보다 큰 숫자가 적힌 카드 중 가장 작은 숫자가 적힌 카드를 내면 됩니다.
여기서 이미 낸 숫자인지 확인하는 방법은 분리 집합을 사용하는 방법이 있겠으며, 분리 집합의 루트는 가장 큰 값으로 해두면 특정 카드를 골랐을 때 손에 존재하지 않는다면 자동으로 그보다 큰 숫자 중 자신이 가진 가장 작은 카드를 골라줄 것입니다. 이 규칙에 따라 K번 출력하면 됩니다.
PS알못 OrbitHv의 PS