https://www.acmicpc.net/problem/4716
문제요약
- 팀마다 필요한 풍선이 있고, 두 지점에서 가지고 올 수 있음. 물론 두 지점에서 가지고 오는 비용이 각각 있음(하나 옮길때마다 드는 비용)
- 각지점마다 풍선이 있음. 두 지점 풍선의 합은 충분함. 합이 충분하다는 이야기이지 한쪽에서만 가져가면 물론 부족할 수도 있음
- 팀 : 1000개, 풍선 : 각각 1만개
- 최소 비용 구하기
접근법
- 기회 비용을 생각해야함
- 어느 지점에서든 풍선을 가지고 와야할텐데, 한쪽을 포기했을때 드는 비용만큼이 추가 비용일 것임
- 즉 각각의 풍선마다 (A에서 가져왔을때, B에서 가져왔을때)를 비교해서 한쪽을 포기했을때의 기회비용을 계산해서 기회비용 오름차순으로 정렬을 하면
- 기회비용이 큰 것부터 유리한 곳에서 가져오게 하는 것이 전체적으로 유리해짐
구현
- 구현은 다른 사람 간결한 코드를 봐서 기록해둠
- 정렬이후에 A 또는 B에서 가져오는 처리를 코드로 나열했는데 수식으로 깔끔해질 수 있음
- A에서 가져오는 개수를 x로 두면 B에서 가져오는 개수는 k - x개임
- A < B이면 min(k, A), k - min(k, A)가 되고
- B > A이면 k - min(k, B), min(k, B) 처리를 해야하는데 그럴 것 없이
- A < B 이면 x = min(k, a), B > A 이면 x = k - min(k, B)로 두고
- 나중에 계산할때, x, k - x로 처리하면 됨
newbieski