문제 설명
•
크기가 N인 배열 2개를 적절하게 재배열해서 합의 최소값을 구하는 문제
예제 입력/출력
•
입력1
5
1 1 1 6 0
2 7 8 3 1
Plain Text
복사
•
출력1
18
Plain Text
복사
•
입력2
3
1 1 3
10 30 20
Plain Text
복사
•
출력2
80
Plain Text
복사
•
입력3
9
5 15 100 31 39 0 0 3 26
11 12 13 2 3 4 5 9 1
Plain Text
복사
•
출력3
528
Plain Text
복사
제약 조건
•
•
배열의 원소
문제 풀이
“작은 숫자와 큰 숫자를 곱한 것의 합은 항상 최소로 나오지 않을까?”
•
모든 경우를 살펴 보자 (브루트 포스)
◦
◦
최악의 경우 → 불가능
•
두 배열을 작은 숫자와 큰 숫자순으로 정렬해서 매칭 시켜보자. (그리디)
◦
A배열은 오름차순, B배열은 내림차순 →
문제에서는 B에 있는 수는 재배열하면 안 된다. 라고 했지만, 배열 2개를 모두 재배열할 수 있다고 생각해도 무방하다.
왜냐하면, A와 B를 모두 재배열해서 나올 수 있는 경우는 A만 재배열하는 경우에도 나올 수 있기 때문이다.
풀이 코드
N = int(input())
arr_A = list(map(int, input().split()))
arr_B = list(map(int, input().split()))
arr_A = sorted(arr_A)
arr_B = sorted(arr_B, reverse=True)
ans = 0
for a, b in zip(arr_A, arr_B):
ans += a * b
print(ans)
Python
복사
심화 내용
그리디적인 풀이의 타당성 증명
알아두면 좋은 내용들
파이썬의 zip() 함수