[BOJ 9576, Python 3] 책 나눠주기

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

9576번: 책 나눠주기

 

 

풀이

일단 정렬해야 하는 것은 아실겁니다. 다행히도 정렬할 수 있는 경우의 수가 5가지 밖에 없어서 모두 확인해볼 수 있습니다.

오름차순은 번호를 작은 것부터 주는 것이 최적해이니 그렇게 주고, 내림차순은 반대로 번호가 큰 것부터 주는 것이 최적해이므로 그렇게 준다고 가정해봅시다.

 

1) a기준으로 오름차순

1 2

1 3

2 2

이렇게 하면 답은 2로 나오지만 실제 답은 3임

 

2) a기준으로 내림차순

2 3

1 2

1 2

답은 2로 나오지만 실제 답은 3임

 

3) b기준으로 오름차순

반례를 찾을 수 없음

 

4) b기준으로 내림차순

1 3

2 3

2 2

답은 2로 나오지만 실제 답은 3임

 

5) b - a로 오름차순(내림차순은 당연히 최적해가 될 가능성은 없으니 생략)

1 2

2 3

3 4

1 3

답은 3으로 나오지만 실제 답은 4임

 

 

3번째를 제외하고 반례는 전부 빠르게 확인할 수 있어서 답을 구할 수 있습니다.

제대로된 증명은 못하겠네요.

 

코드

저는 공항 문제랑 비슷한 문제인줄 알고 유니온 파인드를 사용하였는데, N의 값이 작아서 그냥 for문으로 해도 충분히 돌아갑니다.

def find(x):
    if x == parent[x]: return x
    parent[x] = find(parent[x])
    return parent[x]
 
def merge(x, y):
    x = find(x)
    y = find(y)
    parent[x] = y
 
for _ in range(int(input())):
    n, m = map(int, input().split())
    parent = [i for i in range(n+2)]
    arr = sorted([[*map(int, input().split())] for _ in range(m)], key=lambda x:x[1])
    ans = 0
    for i in range(m):
        a, b = arr[i]
        val = find(a)
        if val <= b:
            merge(val, val+1)
            ans += 1
    print(ans)