[BOJ] 1026번: 보물

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


직관적으로도 당연하지만 A를 내림차순으로 정렬하고 B를 오름차순으로 정렬해서(혹은 A를 오름차순으로 정렬하고 B를 내림차순으로 정렬해서) 매칭을 시켜줄 때 곱의 합이 최소가 됩니다. 재배열부등식이라고 이름 붙은 정리이며 귀납법을 이용해 증명할 수 있습니다.


https://github.com/encrypted-def/BOJ/blob/master/1026.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 2167번: 2차원 배열의 합  (0) 2017.12.31
[BOJ] 2442번: 별찍기 - 5  (0) 2017.12.31
[BOJ] 1085번: 직사각형에서 탈출  (0) 2017.12.31
[BOJ] 1009번: 분산처리  (0) 2017.12.31
[BOJ] 1026번: 보물  (0) 2017.12.31
[BOJ] 2193번: 이친수  (0) 2017.12.31
[BOJ] 1004번: 어린 왕자  (0) 2017.12.31
  Comments
댓글 쓰기