[백준/31411] 대회 개최 (Python)

Problem : https://www.acmicpc.net/problem/31411

31411번: 대회 개최

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:18:41

 

---

 

문제 설명

 

 

용범이는 보라매컵에 문제를 출제하기 위해 서로 다른 N가지 종류의 알고리즘 문제들을 각각 K개씩, 총 NxK개의 문제를 만들었다. 그중 i번째 알고리즘의 j번째 문제의 난이도는 d_ij이다. 그러나 만든 문제를 모두 내기에는 대회 시간이 부족했기에, 서로 다른 N개의 알고리즘마다 각각 하나의 문제씩 총 N개의 문제만 내고자 한다.

또한 용범이는 문제의 난이도가 급격하게 상승하는 것을 방지하기 위해, 난이도 커브를 최소화하고자 한다. 난이도 커브는 대회의 i번 문제의 난이도를 x_i라 할 때 |x_1 - x_2| + |x_2 - x_3| + ... + |x_N-1 - x_N|라고 정의한다. 단, N = 1일 때의 난이도 커브는 0으로 정의한다.

용범이를 도와 N개의 문제들의 순서를 적절히 배치할 때 난이도 커브의 최솟값을 구해주자.

 

 

입력 및 출력

 

입력

 

첫 번째 줄에 알고리즘의 개수 N과 알고리즘마다 만든 문제 개수 K가 공백으로 구분되어 주어진다. (1 <= N, K <= 1,000)

이후 N개의 줄에 걸쳐, i+1번째 줄에 i번째 알고리즘의 j번째 문제의 난이도를 의미하는 정수가 공백으로 구분되어 주어진다. (1 <= d_ij <= 100,000)

 

출력

 

N개의 문제들의 순서를 적절히 배치할 때 난이도 커브의 최솟값을 출력한다.

 

입력 예시

 

3 3
7 2 3
6 9 5
1 4 3

 

출력 예시

 

2

 

 

---

 

풀이

 

난이도 커브는 같은 문제가 주어졌을 경우 난이도가 정렬된 상태일 때 제일 작다는 걸 알 수 있다. 이 때의 난이도 커브값은 x_max - x_min값이 된다.

 

이 점에 착안해서, 모든 문제를 인덱스 정보를 담아 정렬하자. 우리는 어떤 임의의 x_max, x_min값이 주어졌을 때, 이 x_max와 x_min값 사이의 값들에 N개의 인덱스가 모두 존재한다면 이 난이도커브로 문제를 제출할 수 있다는 사실을 발견할 수 있다. 이를 투 포인터로 풀이하여, 모든 값들에 대해 이 문제 여부를 참조하자. 한 번의 투 포인터에 O(d)의 시간복잡도가 소요되며(d <= 100,000), 이와는 독립적으로 O(NK) 시간복잡도로 문제들의 인덱스를 카운팅하게 된다. 즉 O(d + NK)시간복잡도로 문제를 해결해볼 수 있다.

 

풀이 코드

import sys
input = sys.stdin.readline
MAX = 10**6+1

N, K = map(int, input().split())
index = set()
counter = [[] for _ in range(MAX)]

for i in range(N) :
  for j in map(int, input().split()) :
    counter[j].append(i)
    index.add(j)

index = sorted(index)
matched = 0
visited = [0]*N

def update(idx, mode) :
  global matched
  for c in counter[idx] :
    if mode == 1 :
      if not visited[c] :
        matched += 1
      visited[c] += 1
    else :
      visited[c] -= 1
      if not visited[c] :
        matched -= 1

l, r = 0, -1
ans = MAX
while r < len(index) :
  if matched < N :
    if r == len(index)-1 :
      break
    r += 1
    update(index[r], 1)
  else :
    ans = min(ans, index[r] - index[l])
    l += 1
    update(index[l-1], -1)
print(ans)

풀이 완료!