dkim   2년 전

"출력" 항목에서 다음을 요구하고 있습니다.

입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수 쌍이 여러 개 있는 경우에는 두 자연수의 합이 최소가 되는 두 수를 출력한다.

합이 최소가 되는 그런 쌍을 구하는 단순한 방법은 각 쌍의 합을 구하고 그 결과를 비교하는 것일 겁니다.

그런데, 여러 합격 코드(예를 들어, https://www.acmicpc.net/source... https://www.acmicpc.net/source... https://www.acmicpc.net/source... 등)에서 실제로는 각 쌍의 합을 구하고 비교하는 과정을 생략하고 있습니다. 아마 그런 합이 최소가 되는 쌍은 그 차가 최소가 되는 쌍이기도 하다는 성질을 직/간접적으로 사용하고 있는 듯합니다.

그 성질을 수식으로 표현하면 다음과 같을 겁니다:

네 자연수 A, B, X, Y가 주어졌을 때, A * B = X * Y이고 |A - B| <= |X - Y|이면, A + B <= X + Y이다.

맞는 명제인 것 같기는 한데, 증명에 애를 먹고 있습니다. 증명 혹은 반례를 제시해주실 수 있는 분 계신가요? 감사합니다.

chogahui05   2년 전

어렵게 생각하지 마시고. 이렇게 한 번 생각해 보시겠어요?

B<A이고 Y<X라고 가정하면, A-B<=X-Y로 풀 수 있어요.


그 다음에, 네 자연수 A,B,X,Y는 각각 0보다 큰 자연수이므로, 산술 기하 평균을 적용해도 됩니다.

(a+b)/2 >= sqrt(ab)였나. 아무튼 그럴 건데..

이것은 a=b일 때 성립합니다.


아니면 지금 xy = r일 때, x+y의 최솟값을 구하라는 거잖아요? 문제가.

y = r/x로 놓으면 x+y = x + r/x로 놓을 수 있습니다. 이 값이 어디서 최소가 되는지는 간단한 미적분을 이용하면 가능하죠.


f(x) = x+r/x로 놓으면, f'(x) = 0이 되는 지점에서 최솟값을 가지는데. (도함수 그려보면 아시겠지만 -로 갔다가 0이 되었다가 +이 되는 개형입니다. x>0일 때)

나머지는 잘 해석하시면 무난하지 않을까 싶습니다.
 

chogahui05   2년 전

아.. 16인 경우가 있으니까.. 

B<=A이고 Y<=X라고 해야겠네요. 흑..

dkim   2년 전

@chogahui05  말씀하신 대로, 도함수 f'(x)가 1 - r / x2으로서 (0, sqrt(r)) 구간에서 항상 음수값을 가지네요. 따라서, 원래 함수 f(x)는 그 구간에서 강한 단조 감소임(strictly decreasing)을 확인할 수 있었습니다.

덕분에 깔끔하게 이해했습니다. 감사합니다.

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