[백준] 24892. 이차 함수

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

문제 요약

• 2차 함수가 주어지고(${f(x) = (x-a)(x-b)}$
• 그래프 위에 n + 1 꼭지점으로 만들어진 볼록 다각형의 최대 넓이(x 구간이 n 등분) : ${p\over q}$ 서로소인 값 구하기(mod 1000000007)
• a, b, n : < 1000

접근법

• 2차함수는 다들 모양이 비슷할테니 ${-(x+k)(x-k)}$ 형태라고 생각(또는 ${-x(x-k)}$)
• 잘은 모르겠지만 구간이 동일하게 나눠지면 최대일 것 같음
  • 2개구간 => 꼭지점을 지나는 삼각형(x=0)이 높이가 가장 크니까 최대
  • 3개 구간 => 절반 나누어서 한쪽을 고려하고, 사다리꼴이라고 생각하면 넓이는 ${{(k+x)f(x)\over2} = {-(x+k)(x+k)(x-k)\over2}}$
  • 넓이 함수를 미분하면 ${-(3x^2+2kx-k^2) = -(3x-k)(x+k)}$
  • 넓이함수의 볼록하는 지점을 구할 수 있고 ${x={k\over3}}$에서 위로 볼록 하게 되면서 [0, k] 구간에서 최대임을 알 수 있음
  • 반대쪽 부분도 마찬가지일테고 ${(-k, -{1\over3}k, {1\over3}k, k)}$로 나누면 최대가 될 것 같음
• n이 입력으로 주어지면 ${f(x) = x(x-n)}$ 함수에서 구간을 1씩 나누어서 넓이를 구해봄(연속하는 사다리꼴 넓이가 됨)
• 그리고 원래 함수인 ${f(x) = (x-a)(x-b)}$와 넓이 비를 생각해보면..세제곱 비율이 됨
  • 넓이를 구할때 ${x * f(x)}$ 방식으로 구하는데, f(x)가 2차함수가 되어서 결과적으로 도형의 x축 길이 비의 세제곱이 됨
  • ${S : S' = (b-a)^3 : n^3}$
• GCD를 구하고 모듈러 역원을 구해서 곱하고 하면 답이 나옴

후기

• 공식해설을 보면 증명있고, 적분 + 젠센 부등식이라는 것이 보임
• 문제를 접근할때 3개 구간을 엄밀하게 확인하지 못했음 => 포물선의 한쪽을 사다리꼴로 만들어서 3차함수를 구하고, 3차함수가 언제 최대가 될까? 를 고민. 그런데 비뚤어진 사각형은 왜 안될까??
• 증명이 쉽지는 않은데 그냥 감으로 풀어도 되는건가...