'공유기설치' 태그의 글 목록

안녕하세요. 백준에서 chogahui05로 활동하고 있는 조경완입니다. 백준의 공유기 설치 문제는 많이 풀어보셨을 겁니다. 정확히 말하면, N개의 point가 있고, 그 중, C개를 설치하려고 할 때, 가장 인접해 있는 두 공유기 사이의 거리를 최대화 하라는 문제입니다. 어렵네요. 이를, 먼저 결정 문제로 바꾸어 봅시다. 그러면, 먼저 f(x)의 값을 어떻게 구해야 할 지 생각해 봅시다. N개의 집을 x 좌표 오름차순으로 정렬했다고 해 봅시다. 그러면 첫 공유기는 어디에 설치해야 할까요? 1번째 집에 설치해야 합니다. 왜 그럴까요? 문제 조건에 따르면, 같은 x좌표를 가지는 집은 없다고 했습니다. 그렇기 때문에, 집이 n개가 있고, i번째 집의 위치를 x[i]라고 하면, 아래의 식이 성립합니다. 이는 집..