새소식

PS/백준

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

  • -

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

 

31411번: 대회 개최

용범이는 보라매컵에 문제를 출제하기 위해 서로 다른 $N$가지 종류의 알고리즘 문제들을 각각 $K$개씩, 총 $N\times K$개의 문제를 만들었다. 그중 $i$번째 알고리즘의 $j$번째 문제의 난이도는 $d_{ij}

www.acmicpc.net

 

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)

풀이 완료!

Contents

포스팅 주소를 복사했습니다

이 글이 도움이 되었다면 공감 부탁드립니다.