2110번 - 공유기 설치
답이 될 수 있는 경우는 매번 다양할 텐데
다른 분들이 작성하신 코드들을 보면, 공유기 설치 가능 여부를 판별할 때에 맨 첫번째 집에는 항상 공유기가 설치된 것으로 가정하더군요.
그런데 공유기를 2번째 위치부터 놓을 수도 있고, 3번째 위치부터 놓을 수도 있는 걸텐데
(1번째에 공유기가 있다고 가정했을 때에는 답이 존재하지 않고, 그 외 위치부터 공유기가 시작되는 경우만 답이 되는, 그러한 확실한 "반례"는 저도 찾지는 못했습니다만...)
항상 1번째에 공유기를 위치시키고서 코드를 전개하는 것이 안전한가요? 유의미한 차이가 없어서 그런가요? 그렇다면 이유도 궁금합니다.
간단히 말하면 손해를 보지 않기 때문입니다.
최적으로 되도록 공유기를 C개 설치했는데 첫 번째 집에 설치를 안 해놓았다고 칩시다. 그러면 맨 왼쪽 집에 있는 공유기를 첫번째 집에 옮기면 공유기 사이의 거리가 멀어지니까 당연히 가장 인접한 두 공유기 사이의 거리가 늘면 늘지 줄진 않습니다. 따라서 맨 첫번째 집에 공유기를 설치하는 최적해가 언제나 존제하므로 맨 첫번째 집에 무조건 설치한다고 가정해도 됩니다.
sait2000님, 답변 감사합니다. 결국 핵심은, "이 문제의 답인 '간격의 최댓값'을 구하는 데에 있어서는 공유기를 맨 처음에 놓더라도 항상 답(최적해)을 구할 수 있다"인 것이로군요.
관련 내용을 다룬 질문이 있어서 링크 첨부합니다
https://www.acmicpc.net/board/view/31633
댓글을 작성하려면 로그인해야 합니다.
cadenzah 5년 전 1
답이 될 수 있는 경우는 매번 다양할 텐데
다른 분들이 작성하신 코드들을 보면, 공유기 설치 가능 여부를 판별할 때에 맨 첫번째 집에는 항상 공유기가 설치된 것으로 가정하더군요.
그런데 공유기를 2번째 위치부터 놓을 수도 있고, 3번째 위치부터 놓을 수도 있는 걸텐데
(1번째에 공유기가 있다고 가정했을 때에는 답이 존재하지 않고, 그 외 위치부터 공유기가 시작되는 경우만 답이 되는, 그러한 확실한 "반례"는 저도 찾지는 못했습니다만...)
항상 1번째에 공유기를 위치시키고서 코드를 전개하는 것이 안전한가요? 유의미한 차이가 없어서 그런가요? 그렇다면 이유도 궁금합니다.