[백준] 21761. 초직사각형

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

접근법

• 대회 문제라 공식 해설은 있지만, 내 접근법을 기록해봄
  • https://koi.or.kr/assets/koi/2021/1/solutions/h2-answers.pdf
• A,B,C,D의 증가는 큰 것부터 사용하는 것이 유리함
• 최종 결과를 도출했을때 바로 이전 상태를 생각해보면 엄밀하지는 않지만 다음과 같이 대략적으로 증명을 해볼 수 있음
  • 최종 상태 $S_k$, 바로 이전 상태 $S_{k-1}$, 그리고 이때 사용한 증가는 $A'$
  • $S_{k-1}$이 이전상태의 최대가 아니라고 가정하면
    • $A'$를 제외하고 $S_{k-1}$를 최대로 만들 수 있으면 만들면 $S_k$가 더 커짐(모순)
    • $A'$를 이용해야 $S_{k-1}$를 최대로 만들 수 있으면 만들고 다른 값을 "교환"해서 마지막에 사용하면 결과가 나빠지지는 않을 것임
  • 이전상태가 최대값이면 결과가 좋아지거나 나빠지지는 않은....이런 증명
• 값을 선택하는 구현
  • 증가분을 선택했을때 값이 얼마나 증가하는지를 계산해보면
  • $(A' * B * C * D)$와 $(A * B'* C * D)$를 비교한다고 볼때 공통부분인 $(C * D)$는 제거하고 비교하면 long long으로 계산 가능
  • 더 쉬운 방법 : $A -> A'$ 가 되므로 증가 비율은 $A' / A$ 임을 이용해도 됨