균형 잡힌 포장
실버 III의견: 0
선물 포장 공방에 상자 \(N\)개와 뚜껑 \(N\)개가 있다. 상자와 뚜껑에는 각각 크기가 적혀 있다.
모든 상자에 뚜껑을 정확히 하나씩 짝지어 덮어야 한다. 상자 크기 \(a\)에 뚜껑 크기 \(b\)를 짝지으면 \(|a - b|\)만큼 모양이 어긋난다.
짝짓기를 잘 했을 때, 어긋남의 합의 최솟값을 구하여라.
- \(1 \le N \le 100\,000\)
- 모든 크기는 \(0\) 이상 \(10^9\) 이하의 정수이다.
첫째 줄에 상자의 수 \(N\)이 주어진다.
둘째 줄에 상자의 크기 \(N\)개가 공백으로 구분되어 주어진다.
셋째 줄에 뚜껑의 크기 \(N\)개가 공백으로 구분되어 주어진다.
어긋남의 합의 최솟값을 출력한다. 답이 \(32\)비트 정수 범위를 넘을 수 있음에 주의하여라.
3
1 5 3
4 2 2
3
상자 \(1\)에 뚜껑 \(2\), 상자 \(3\)에 뚜껑 \(2\), 상자 \(5\)에 뚜껑 \(4\)를 짝지으면 어긋남이 \(1 + 1 + 1 = 3\)으로 최소이다.
2
10 20
20 10
0
크기가 같은 짝끼리 맞추면 어긋남의 합이 \(0\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
균형 잡힌 포장
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
균형 잡힌 포장