lego0901   2년 전

전봇대 간의 간격을 d라고 할 때 (편의 상 n = N - 1 이라 하겠습니다. N은 전봇대의 개수)

move(d) = |d - x_1| + |2 * d - x_2| + |3 * d - x_3| + ... + |n * d - x_n|

값을 최소화하는 문제입니다. 이 식을 간단히

move(d) = |d - x_1| + 2 * |d - x_2/2| + 3 * |d - x_3/3| + ... + n * |d - x_n/n|

으로 변형하여 생각했습니다. y = k * |x - b| 의 그래프가 (b,0)을 기준으로 왼쪽으론 기울기가 -k, 오른쪽은 기울기가 k인 그래프이므로

move 함수는 d->-무한대 이면 기울기가 -(1+2+...+n), d->+무한대 이면 (1+2+...+n) 인 그래프가 그려질 것입니다.

또한 d 좌표값 x_i/i 를 기준으로 오른쪽 그래프는 왼쪽 그래프보다 기울기가 2 * i 만큼 증가해 나타날 것입니다.

왜냐하면 y = i * |d - x_i/i| 그래프는 극점 (x_i/i, 0)을 기준으로 오른쪽 편의 기울기가 왼쪽보다 2 * i 만큼 더 커지기 때문입니다.


그래서 x_i/i 값 크기로 정렬한 다음, 그 값이 작은 순서대로 천천히 읽어가면서

d = x_i/i 값 이후 기울기의 변화를 체크하는 코드를 작성하였습니다.

slopesum, 즉 move 함수의 기울기는 초기에 -n * (n+1) / 2 가 될 것이며, x_i/i 점을 읽을 때 마다 기울기를 2 * i 씩 더해줬습니다.

Slopesum 이 처음으로 음이 아닌 수가 되는 d = x_i/i 위치에서 move 함수는 극점을 가지게 될 것입니다.

그 x_i/i 값은 정수가 아닐 가능성도 있으므로

floor(x_i/i), floor(x_i/i) + 1 을 d 값으로 두고 move(d) 값이 작은 것을 출력하도록 했습니다. (move가 연속 함수기 때문입니다.)


테스트 케이스들 나름 만들어 넣어보기도 하고, move 함수를 그래프로도 그려봤는데 크게 틀린 점을 못 찾겠습니다.

어떤 예외가 있을까요?

고수님들 부탁 드립니다.. ㅠ

chogahui05   2년 전

풀이에 대해서는 언급할 게 없는 거 같습니다. 솔직히 접근 방법은 맞습니다.

문제는 기능이 복잡하다는 건데요. 정수로 자르는 연산(?) 을 수행하고 있죠. 물론 대부분의 케이스에서는 맞고

ideone 사이트에서도 제 소스와 비교해서 맞는 답을 출력하는 것을 확인했지만.. 만에 하나가 걸릴 지도 모르지요. 

(어디서 예외가 걸리는 지는 제가 집 가서 조금 큰 데이터를 돌려보겠습니다.. 그만큼 예외 찾기가 너무 어렵다는 겁니다.. 4시간동안 ideone에서 손으로 찾으려고 해 봐도 안 나오더라고요.. ㅠㅠ)


절댓값 함수 f(x) = |ax+b|가 있을 때 ax+b가 양수면, 그냥 그대로 ax+b가 나오고요. 음수면 -ax-b가 나오잖아요.

그리고 move 함수는 연속 함수고요. move의 기울기 값은 x가 증가할수록 증가하지요.

뭔가 정렬이 되어 있습니다.


이걸 역이용 하시면 좋을 듯 싶습니다.



lego0901   2년 전

제 코드에 관심 가져주셔서 정말 감사드립니다.

풀이의 전체적인 맥락은 답변 내용과 거의 상동 한 것 같습니다.

허나, 생각보다 문제는 간단했네요. 최대 범위가 100,000 인 n 을 int 형으로 선언해둔 채 45 번째 줄에서 n * (n + 1) 을 썼던 것이 문제였네요.

ll slopesum = -((ll) n) * (n + 1) / 2;

이렇게 형 변환을 통해 바로잡았더니 AC 띄었습니다.

chogahui05   2년 전

진짜 예외 잡기가 어려웠단 건.

풀이 방법이 맞으셨다는 것이지요.. 응? 아무리 넣어도 잘 되는데??


보통, 빡세게 넣어보면 1-2시간 내에 나오거든요. 작은 테스트 케이스만 넣어볼 때는요.

이상하게 그 경우에 대해서는 모두 제 프로그램과 같은 결과를 출력하셨으니..


접근 방식이 괜찮더군요. 완전히 틀렸다고 하기도 뭐하고.. 제가 아무리

종이 몇 장에 반례를 찾으려 노력했지만.. 안 되었으니..


ps.

설마 설마 했는데..

풀이는 (처음 제가 답변한 것처럼) 굳이 언급하지 않아도 될 정도로 괜찮았습니다.

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