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

문제

https://www.acmicpc.net/problem/2212

풀이

일단 문제를 이해하는 것에 시간이 좀 들었다.
집중국를 어디에 두어야 최솟값을 구해야할 지 머릿속으로 생각해보고 있었다.

이 문제에서는 기존에 주어진 입력을 정렬해도 상관없겠다 생각해서 정렬해서 생각해보았다.
[1, 3, 6, 6, 7, 9]

2에하나, 7에하나 두는게 정답인데 멍청하게 6이 두개일 때 6에서 7을 수신하는데 드는 거리를 2라고 생각했다;; (두개여서..)
이 부분에서 시간을 많이 잡아먹었다.

결국 구간을 나눠야 되는 것이라고 생각했고 구간은 차이가 가장 큰 부분을 나눠주면 된다고 생각했다.
1번 예제에서는 구간을 두개로 나눠야 하므로, 차이가 가장 큰 부분을 빼주면 두 구간으로 나누게 된다.
[2, 3, 0, 1, 2] 라면 3, 6의 차이가 3이므로 가장 크다.

그렇다는 것은 3과 6의 사이를 나누어 주어야된다는 뜻이므로 다음과 같이 될 것이다.
[1, 3], [6, 6, 7, 9]
이는 [2, 3, 0, 1, 2] 에서 [2] [0, 1, 2] 나눠진 것을 의미하고, 그냥 구간에서 가장 큰 값 - 가장 작은 값 해주면 된다.
사실 이것은 [2, 0, 1, 2] 의 합과 동일하다 ㅎ

이렇게하고 제출하였는데 런타임에러가 나서 엥 뭐지했다.
센서의 개수보다 집중국의 갯수가 크거나 같을 때가 문제가 되었다. 이 경우에는 답이 무조건! 0이다.

소스코드

후기

이상한 곳에서 애먹었던 문제.
이거랑 되게 비슷한 문제를 풀어봤어서 갑자기 머릿속에 팍 떠올랐다.