[#13164] 행복 유치원

문제

#13164 행복 유치원
Gold5
적용 알고리즘: Greedy 알고리즘

---

풀이 방법

• 입력받은 학생들 간의 차이를 구한다.
• 차이들 중 가장 작은 간격부터 하나의 그룹으로 만든다.

### 코드 흐름

1. 학생들 사이 키의 간격을 구한다.
2. 이를 오름차순으로 정렬한다.
3. 작은 수부터 num - group수만큼 더한다.

코드

import sys

input = sys.stdin.readline

num, group = map(int, input().split())
member = list(map(int, input().split()))

dist = [member[i + 1] - member[i] for i in range(num - 1)]
dist.sort()
print(sum(dist[:num-group]))

체감 난이도: 4.6/5
아이디어가 관건인 문제인것 같다. 처음에 테스트 케이스에 대한 정답은 나왔지만 자꾸 시간초과가 떠서 결국 풀이를 찾아보았다. 그냥 정렬된 숫자에서 특정 개수만 뽑아내면 되는 간단한 문제였다. 하지만 아이디어를 생각해내는 것 자체가 좀 힘들었던 문제이다.

---

[이전 나의 풀이]
import sys를 했는데도 시간초과가 나는 것을 보니, 너무 큰 수에 대해서 감당을 못 하는 것 같다.

import sys

input = sys.stdin.readline

num, group = map(int, input().split())
# member = [int(m) for m in input().split()]
member = list(map(int, input().split()))

dist = [member[i + 1] - member[i] for i in range(num - 1)]

cnt = 0
n = num - group
for _ in range(n):
    min_idx = dist.index(min(dist))
    if (min_idx == 0 and len(dist) != 1):
        dist[min_idx + 1] += dist[min_idx]
    elif (min_idx != 0 and min_idx == len(dist) - 1):
        dist[min_idx - 1] += dist[min_idx]
    else:
        dist[min_idx + 1] += dist[min_idx]
        dist[min_idx - 1] += dist[min_idx]

    cnt += dist[min_idx]
    del dist[min_idx]

print(cnt)