[백준] 3769. 최댓값

https://www.acmicpc.net/problem/3769

문제요약

• 조건을 만족하는 실수 x의 최대값 구하기
• 조건 : root어쩌고.....

접근법

• root에 너무 현혹되면 어지러움
• 전부 같은 값이면 최소값은 되겠지만 최대값은 아님
• ${\sqrt{a}}$가 많을 수록 좋을 것 같음
  • +/-가 같은 지점이 1인데
  • 1이 여러개 있는것보다 2가 하나있는데 더 유리하다...이런 접근법
• a가 0보다 큰 정수이기 때문에 ${{-1\over\sqrt{a}}}$의 절대값이 1이하임
• 이 단서가 왜 중요하냐면 ${\sqrt{a}}$를 하나 만들고 ${{-1\over\sqrt{a}}}$ 들로 상쇄한다는 아이디어를 도출할 수 있기 때문이다.
• 이렇게 정리해볼 수 있다.
  • 이것 저것으로 구성이 되어있겠지만, ${\sqrt{a}}$가 많으면 좋기때문에 최대 갖을 수 있는 개수를 x개라고 하면
  • 나머지 값으로 상쇄를 해야하는데, 상쇄할때도 가능한 큰 값으로 상쇄를 하면 좋겠고, ${{-1\over\sqrt{a}}}$의 개수를 y개라고 하면
  • ${x\sqrt{a} + y{-1\over\sqrt{a}} = b\sqrt{a}}$
  • 정리하면 ${ax - y = b}$
  • 그리고 ${x + y <= m}$도 만족해야함. 여기서 왜 작거나 같게 되냐면, 0도 가능하기 때문에 딱 맞춰서 값을 못만들 수도 있기 때문이다. b가 조금 더 큰 경우도 가능하다는 의미
• 방정식과 부등식을 정리하면 x, y의 값을 구하게 되는데, 그 다음이 문제이다.
• 남는 값들을 가지고 어떻게 최대값을 만들 수 있는가?
  • 예시로 주어진 테스트케이스에서는 3개의 값이 남는다.
  • 처음에는 단순하게 -1, 1을 생각했지만 일단 값의 조건에 맞지도 않을뿐더러 맞더라도 더 괜찮은 값이 있다. ==> 2, -1, -1 같은...
  • 확장해보면 3개로 조건을 만족하면서 구성할 수 있는 방법은
    • 하나가 가장 크고, 나머지들은 작으면 됨
    • ${{-1\over\sqrt{a}}}$, ${{-1\over\sqrt{a}}}$, ${{2\over\sqrt{a}}}$
  • 비슷한 생각으로 ${\sqrt{a}}$를 1:2로 나누어서 양쪽의 절대값이 같고, 부호가 다르게 만들어도 됨