[항해99]99클럽 코테 스터디 18일차 TIL + 백준 2212

99클럽 코테 스터디 18일차 TIL + 백준 2212

오늘의 학습 키워드

• 백준 2212
• 센서
• 그리디 알고리즘

공부한 내용

• 정렬을 활용
• 센서 위치를 입력받아 오름차순 정렬
• 인접한 센서 사이의 거리를 전부 구해 dist 리스트에 저장 후 내림 차순 정렬
• 센서들을 k개의 구간으로 나눠야 하므로, k-1번만큼 반복을 돌며 값이 가장 큰 원소부터 차례로 제거
• 남은 원소들의 합을 구하여 출력한다.

# 백준 2212
# 센서

import sys
input = sys.stdin.readline

N = int(input())
K = int(input()) # 집중국의 개수

# N개 센서의 좌표
sensors = list(map(int, input().split()))
sensors.sort() # 센서의 좌표를 정렬

dist = [] # 각 센서 사이의 거리

for i in range(1, N):
    dist.append(sensors[i] - sensors[i-1])
dist.sort(reverse=True)

for _ in range(K-1):
    if dist:
        dist.pop(0)

print(sum(dist))

오늘의 회고

• 그리디 문제가 익숙치 않다. 어떤 아이디어로 풀어야할지 익숙치가 않음...