[BOJ] 16566 카드 게임

date

Aug 23, 2023

slug

boj-16566

author

status

Public

문제 링크

https://www.acmicpc.net/problem/16566

문제

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

N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.

N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다.

철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.

철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번호가 큰 사람이 이긴다. 이 동작을 K번 해서 더 많이 이긴 사람이 최종적으로 승리한다. 한 번 낸 카드는 반드시 버려야 한다.

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

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

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

문제풀이

pypy3는 메모리 초과가 나서 python3로 제출하니 통과헀다.

검색을 해보니 parametric search로 빠르게 풀 수 있는 것으로 보였는데, 난 아직 이게 익숙하지못해서

대깨로 풀었다.

Union-Find 구조를 약간 변형한것으로

p배열의 인덱스가 나타내는 값이 다음 출력값이 되게하면된다.

이때 사용되지 않는 카드가 있을 수 있는데, 이것을 Union으로 묶어서 처리하면된다.

프로세스의 전체 흐름은 다음과 같다.

blue, red 카드를 입력받고, p배열과 blue카드가 있다는 것을 표시할 arr배열을 초기화한다.

모든 레드카드에 대해서

p배열에 레드카드 값을 m이라고 하고
만약 m이 arr배열, 즉 한번도 사용하지 않은 blue카드라면?

출력 한다 ( red보다 크면서 가장 작은 blue 카드)
그리고 red_card의 p배열을 blue카드의 p배열로 합쳐준다. 즉 red_card가 또 나올수 있는데 이 값을 blue카드의 다음 최솟값으로 합쳐줌
그리고 m에 해당하는 blue카드를 0으로 (사용한것으로) 바꿔준다.

만약 사용했거나 블루카드에 없으면?

다음 블루카드에 있는것을 red와 합쳐줌, 이것을 반복 (~4000000)
이때 find연산이 필요한데 경로압축을 하지않으면 시간초과
계속 찾다가 p배열에 해당하는것이 blue카드이면서 아직 사용하지 않았을 경우 찾은 node를 반환하여, 출력

process를 그림으로 그려보면 빠르게 이해할 수 있다.

파이썬 문제풀이 코드


import sys
# sys.setrecursionlimit(325000)
sys.setrecursionlimit(4000000)
input = sys.stdin.readline
N, M, K = map(int, input().split())

blue = list(map(int, input().split()))
red = list(map(int, input().split()))

arr = [0] * (N+1)
p = [i+1 if i != N else 1e7 for i in range(N+1)] # 자기 자신보다 적어도 1은 크되, 마지막 값보다 큰 것은 없다.

for i in range(len(blue)): # blue card check
    arr[blue[i]] = 1
    
def union(A: int, B: int): # B > A always
    pb = find(B)
    
    p[A] = pb
    
def find(node):
    if p[node] >= 1e7:
        return node
    
    if arr[p[node]] == 1:
        return node
    
    p[node] = find(p[node])
    return p[node]
    
    
for red_card in red:
    m = p[red_card] 
    while True:
        if arr[m] == 1:
            print(m)
            union(red_card, m)
            arr[m] = 0
            break
        else:
            union(red_card, m)
            m = p[m]

            
    
    
#
# 7 6 6
# 2 3 4 5 6 7
# 1 4 2 5 2 5

# 7 6 6
# 2 3 4 5 6 7
# 4 3 2 1 1 1

시간복잡도

O(nlogn)

입력

첫째 줄에 세 개의 자연수 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번째로 낼 카드의 번호가 출력되어야 한다.

예제 입력


10 7 5
2 5 3 7 8 4 9
4 1 1 3 8

예제 출력

알고리즘 분류

자료 구조

이분 탐색

분리 집합