[백준] 센서

시간복잡도 생각해보기

• 10^6이 최댓값이므로 O(NlogN)안에 해결하는 것이 중요하다.
• 배열을 정렬하고 -> O(NlogN) + N-1개의 차를 계산하고O(N) +O(N-K)만큼 차를 더하므로 =>O(NlogN)

풀이 아이디어

• K개의 집중국이 있을 때 연속된 센서 간의 차를 최소한으로 해라 => 그리디
• 1. 센서 좌표 배열을 받아서 연속된 센서 간의 차를 구한다.
• 2. 연속된 센서 간의 차이를 오름차순으로(혹은 내림차순)으로 정렬한다.
• 3. 집중국 개수 K-1 만큼만 배열들을 더해준다.
     
  • 집중국 K를 세워야 한다면 센서와 센서 사이를 K-1 회 뛰어넘을 수 있기 때문이다.
  • 그리고 자기 자신에만 집중국을 세운다면 거리가 0이 되는 것도 생각해야 한다.

의사코드 / 풀이 과정

for(int i=0; i<s.length;i++) {
    s[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(s);
for(int i=0; i<minus.length;i++) {
    minus[i] = s[i+1] - s[i];
}
Arrays.sort(minus);
int answer = 0;
for(int i=0; i<N-K;i++) {
    answer+=minus[i];
}

참고 자료