[BOJ] 2461 대표선수 - Python

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

2461번: 대표 선수

 

참으로 고생 많았던 문제다..

어떻게 풀어야할지 감도 안잡혀서 일단 종이와 펜을 들었다.

그리고 위 예제를 봤다

3 4
12 16 67 43
7 17 68 48
14 15 77 54

음.. 12를 먼저 선택하고 다음줄부터 7 , 17 , 68 ... 이렇게 탐색을 한다?

N^3 이 나올 것이다. 1000이니까.. 10억?? 택도없네

한번 정렬을 해보자

 

3 4
12 16 43 67
7 17 48 68
14 15 54 77

 

음.. 먼저 맨 앞에 12, 7, 14 로 팀을 한다고 생각을 해보자.

그러면 14 - 7 해서 7이 답이 될 것이다.

 

근데 오름차순 정렬을 했으니 여기서 제일 작은 값인 7이 있는 줄!! 여기 바로 옆의 17을 선택한다

그럼 팀이 12, 17, 14 가 되겠지? 그럼 다시 여기서 17-12 해서 5!! 이렇게 점점 줄여나갈 수 있다.

 

이렇게 하면 N*M 개 만큼 보고 heap에 넣고 빼는 logN 만큼 O(NMlogN) 가 되겠다.

 

import heapq

N, M = map(int, input().split())
arr = []
ind = [1] * 1001 # 몇번째 인덱스에 있는 배열을 선택할 건지
maxVal = 0
hq = []
for i in range(N):
    li = list(map(int, input().split()))
    li.sort()
    maxVal = max(maxVal, li[0])
    arr.append(li)
    heapq.heappush(hq, (arr[i][0], i))

res = 10**9
while hq:
    front = heapq.heappop(hq)
    minVal = front[0]
    index = front[1]

    res = min(res, maxVal - minVal)
    if ind[index] == M:
        break
    heapq.heappush(hq, (arr[index][ind[index]], index))
    maxVal = max(maxVal, arr[index][ind[index]])
    ind[index] += 1

print(res)