99클럽 코테 스터디 18일차 TIL: 심화 그리디와 정렬

오늘의 문제: 2212. 센서

문제를 대충 읽어봤을 때는 그래프인가? 그리디인가? 확신이 서지 않았다. 우선 그리디 문제는 저번 문제 풀었던 거처럼 차분히 하나하나 정리하며 읽어보기로 했다.

1. 센서는 N개 설치하였고, K개의 집중국을 설치했다.
2. 집중국은 수신 가능 영역이 따로 있고, 센서들은 하나의 집중국이라도 닿아야 한다.

입력으로 주어지는게 센서이다 보니 집중국의 수신 가능 영역 길이의 합이 어떤 걸 뜻하는지를 먼저 생각해야 겠다 싶었다. 일단 이쯤됐으면 그리디 문제라는 건 바로 파악이 되긴 했다.

결국 문제를 푸는 걸 포기하고 검색했다…

아이디어: 각 센서 사이의 거리를 먼저 계산하자.

집중국이 설치된 지점은 따로 거리가 계산되지 않는다. 따라서 각 지점에 설치했을 때, 어느 지점에 설치하는 게 손해인지를 확인하고 손해인 지점들 기준으로 합을 계산하는 것이다.

n=int(input())
k=int(input())
l=[*map(int,input().split())]
l.sort()

rl=[]
for i in range(n-1):
    rl.append(l[i+1]-l[i])
rl.sort()

print(sum(rl[:n-k]))

이게 왜 정답인지 아직 이해가 되지 않는다. 사실 나머지는 그리디적으로 어느정도 이해가 되는데, 왜 n-k개만 체크하는 것인지 이해가 약간 안된다.

1. n은 전체 센서의 개수, k은 설치할 수 있는 집중국의 개수
2. 그렇다면 n-k는 집중국이 설치되지 않은 센서의 개수 → 무조건 코스트가 발생하게 됨.
3. rl 리스트는 발생할 수 있는 코스트들의 최솟값부터 접근하여 더함.

오늘의 회고

오늘은 어쩔 수 없이 약간의 힌트의 도움을 받았다… 사실 정렬할 아이디어를 못 떠올리기도 했지만 이를 이용할 방법도 떠올려야 해서 이 문제가 코드 길이에 비해 높은 티어를 받았다는 생각이 든다.

그리디는 확실히 티어가 높아지면 높아질 수록 아이디어를 떠올리기 어렵다. 높은 티어 문제를 많이 풀면서 적응해야 겠다.