[BOJ] 16566 카드 게임 (C/C++)

16566번: 카드 게임

문제

철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.

1. N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.
2. N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다.
3. 철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.
4. 철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번호가 큰 사람이 이긴다. 이 동작을 K번 해서 더 많이 이긴 사람이 최종적으로 승리한다. 한 번 낸 카드는 반드시 버려야 한다.

철수는 뛰어난 마술사이기 때문에 본인이 낼 카드를 마음대로 조작할 수 있다. 즉, 카드를 버리고 민수 몰래 다시 들고 온다거나 민수한테 없는 카드를 내기도 한다.

민수는 뛰어난 심리학자이기 때문에 철수가 낼 카드를 알아낼 수 있다. 그래서 민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드를 내기로 했다.

K번 동안 철수가 낼 카드가 입력으로 주어진다. 그렇다면 민수가 어떤 카드를 낼지 출력하라. 단, 민수가 카드를 내지 못하는 경우는 없다고 가정한다.

입력

첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000))

다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 다르다.

다음 줄에 K개의 자연수가 주어진다. i번째 수는 철수가 i번째로 내는 카드의 번호이다. 철수가 내는 카드 역시 1 이상 N 이하이다.

출력

K줄에 걸쳐서 수를 출력한다. i번째 줄에는 민수가 i번째로 낼 카드의 번호가 출력되어야 한다.

---

대충 문제를 읽었을 때 별로 어려워 보이지 않아서 한번 도전해본 플레 문제다. 처음에 문제 제목을 봤을 때에는 DP나 그리디 쪽일 것 같았는데 의외로 전혀 아니었다. 첫번째 아이디어를 떠올리고 무지성으로 코딩하니까 시간 초과가 떴다. 맞는 방법이라고 확신이 들었지만 조금 더 최적화가 필요했다.

 

민수가 낼 카드를 고르기 위해서는 단순히 upper_bound 함수만 사용해도 되겠다고 생각이 들었다. 그리고 낸 카드를 벡터에서 삭제해주면 되겠단 생각이 들어서 sort, upper_bound, erase 함수를 사용해서 구현했다. 하지만 벡터 자체가 배열보다 느리기도 하고 erase 함수를 계속 호출하면서 오버헤드가 커져 시간 초과를 봤다.

 

upper_bound를 쓰기 위해서는 sort까지는 무조건 해야했다. 그래서 생각한 건 카드를 손에서 내려놓는 게 아니라 내고 싶은 카드를 이미 사용했다면 그 카드보다 한 계단만 큰 카드를 내면 될 것 같았다. 그래서 카드를 낼 때 다음에 낼 카드를 미리 골라둔다. 이때 union-find를 사용했다. parent 배열의 값이 인덱스와 같은 경우에는 카드를 낼 수 있는 상태고 아니라면 그 카드는 이미 낸 카드다.

 

 

후기)

플레 문제치고는 쉬웠다는 생각이 든다. 첫번째 방법을 생각해내는 데에는 그리 많은 시간이 걸리지도 않았다. 결국은 최적화를 잘하는 게 포인트였다. solved.ac에서 난이도를 준 사람들의 말들을 보면 union-find를 생각해내는 게 핵심인 것 같다. 그리고 10775 공항 문제랑 비슷한 문제였던 것 같아 찾아보니 5달 전쯤에 풀었었던 문제였다. 하지만 이번 문제를 풀 때 전혀 생각도 안 났다. 진짜 부질없네. 

 

문제 출처가 우리 학교 알고리즘 대회였다. 한번도 안 나가봐서 난이도를 전혀 몰랐는데 한 이 정도 나오는구나 싶었다.