skynet   1년 전

  1. 마을의 위치는 중복이 가능 한 걸까요?
  2. 중복 여부와 상관 없이 (최적경우에서) 각 사람들로 부터 우체국까지의 거리의 합이 long long 크기를 초과하는 경우가 있을 수 있는데 접근을 잘못 하고 있는 걸까요?

portableangel   1년 전

  1. 검증해봤는데, 모든 x값은 서로 다릅니다.
  2. 거리의 합은 직접 구하지 않아도 되며, 그냥 거리의 합이 최소가 되는 위치를 출력하면 됩니다. 물론 거리의 합을 직접 계산할 필요가 없는 풀이가 존재하기 때문에 가능합니다.

skynet   1년 전

음... 제가 생각하기엔 최적값이 [x1, x2] 이렇게 구간으로 나올 수 있고, 답을 x1을 출력 하면 되는데

1. 소트
2. 마지막 마을부터 우체국을 설치
3. 이전 마을 보다 효율성이 떨어지면 이전 마을에 설치

djm03178   1년 전

그렇게 풀 필요가 없습니다. 힌트: 거리를 고려하지 않아도 됩니다.

댓글을 작성하려면 로그인해야 합니다.