-문제:https://www.acmicpc.net/problem/2212
n개의 구간을 k개의 영역으로 나누면 된다고 생각했고, 각 위치의 차이를 이용하는 것이라고 생각했는데
그 다음 구현을 어떻게 할지 몰랐던 문제다
-정답풀이:
기지국이 세션수보다 같거나 크면 모든 지점에 기지국 설치하면 되므로 0을 출력한다
먼저 세션 위치를 다 받아서 작은 것부터 정렬한다
sys.exit()를 빼고 돌렸더니 틀렸다.
0이 출력되고 끝나야하므로 exit()를 선언해줘야 하는 것 같다
인접한 세션끼리의 거리차를 distance 리스트에 넣는다
거리차를 내림차순으로 정렬한 뒤 거리가 가장 긴 것부터 k-1개를 제거하고 남은 길이의 합을 구하면 된다
import sys
n=int(input())
k=int(input())
s=sorted(list(map(int,input().split())))
if k>=n:
print(0)
sys.exit()
distance=[]
for i in range(1,n):
distance.append(s[i]-s[i-1])
distance.sort(reverse=True)
for _ in range(k-1):
distance.pop(0)
print(sum(distance))
'백준 > Greedy' 카테고리의 다른 글
[코딩테스트] 백준 1041번: 주사위 (0) | 2022.02.06 |
---|---|
[코딩테스트] 백준 15904번: UCPC는 무엇의 약자일까? (0) | 2022.02.06 |
[코딩테스트] 백준 15903번: 카드 합체 놀이 (0) | 2022.02.05 |
[코딩테스트] 백준 11497번: 통나무 건너뛰기 (0) | 2022.02.05 |
[코딩테스트] 백준 1213번: 팰린드롬 만들기 (0) | 2022.02.04 |