[python] 백준 30960번: 조별 과제

문제

문제 출처 : https://www.acmicpc.net/problem/30960

조별 과제를 위해서 수강생 $N$명의 사람의 조를 편성하려고 한다. 모든 사람은 정확히 한 개의 조에 속해야 한다. 원래 한 조는 $2$명으로 이루어져야 하지만, $N$이 홀수이기 때문에 단 하나의 조는 $3$명으로 이루어진다. 다른

$\frac{N-3}{2}$개의 조는 $2$명으로 이루어진다.

성공적인 조별 과제를 위해서는 화기애애한 분위기가 중요하다. 각 학생에게는 고유한 학번이 있으며, 어떤 조의 어색함은 해당 조에 속한 사람의 학번 중 최댓값과 최솟값의 차이로 계산된다.

조를 적절히 편성해서, 편성된 모든 조의 어색함의 합을 최소화하자.

입력

첫 번째 줄에 수강생의 수 $N$이 주어진다. $(3 \le N \lt 500\,000;$ $N$은 홀수 $)$ 

두 번째 줄에 각 학생의 학번을 의미하는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$ 주어지는 $A_i$는 서로 다르다.

출력

조를 적절히 편성해서, 편성된 모든 조의 어색함의 합의 최솟값을 출력하여라.

문제 풀이

접근

• N의 최댓값이 500,000 이므로 $N^2$이 넘으면 안된다.
• 차이가 최소화 되어야 하므로 정렬을 해주어야 될 것 같다.
• 풀이가 도저히 생각이 안나서 분류를 확인했다. (그리디 아니면 DP를 예상하고 있었다)

풀이

1. 2개조씩 묶을 때의 누적합 x
2. 3개조가 포함된 누적합 y
3. i가 짝수번째 일때 x와 y를 찾아준다
   

$x = x + A_i − A_i−1$
$y = min(y, x) + A_{i+1} − A_i$

코드

n = int(input())
students = list(map(int, input().split()))
students.sort()

x, y = 0, float('inf')
for i in range(1, n, 2):
    x = x + students[i] - students[i - 1]
    y = min(x, y) + students[i + 1] - students[i]
print(y)

후기

개인적으로 그리디 문제에 약한 것 같다… 그리디인 것을 알고 풀었음에도 답을 찾는데 한참 걸렸다. 막상 풀고나니 코드는 몇줄 안되는게 더 답답하다.