https://www.acmicpc.net/problem/25045
문제 요약
- N개, M개 숫자배열 A, B가 주어지고, Ai - Bi의 합을 최대로. 단 Ai >= Bi
접근법
- 쉽게 생각해보면 sum(A) - sum(B)를 하면 될 것 같지만 Ai >= Bi 를 위배하는 경우가 있을 것임
- A의 가장 큰 것부터 - B의 가장 큰 것부터 하면 될 것 같지만 이 경우는 전체 값이 커지지는 않음. 예외도 있음 : ex) [10], [11, 9]
- A의 가장 큰 것 - B의 적절한 시점부터 큰것 하면 될 것 같지만 예외가 있음 : ex) [1,2,3], [1,2,3]
- A의 가장 큰 것부터 - B의 가장 작은 것부터 하고 싶은데 납득이 안되는 부분들이 있음
- 연결되는 쌍의 숫자가 줄어들 것 같은데 불리하지 않을까?
- 일단 A는 큰것들을 모으고, B는 작은 것들을 모으면 좋겠음
- 이런 생각을 해볼 수 있음
- 최종 답을 구했다고 치면
- (a + a' + a'' + ....) - (b + b' + b'' + ...)
- 나름 잘 구성을 했겠지만 a의 최소 - b의 최대를 주목해보자
- 이 값이 음수이면? 전체합에서 빼는게 유리 : (나머지) + (a최소-b최대)
- 저런 값이 안나오게 하려면... a최대 - b최소부터 해 나가는 것이 유리함
newbieski