알고리즘💻/이분탐색&정렬&분할정복
BOJ 1026번: 보물
호프
2021. 1. 29. 18:59
1026번: 보물
첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거
www.acmicpc.net
아이디어: 정렬
B의 가장 큰 수에 A의 가장 작은 수를 곱하면 된다.
A는 오름차순으로, B는 내림차순으로 정렬한 후 각각 곱한다.
5
1 1 1 6 0
2 7 8 3 1
이 예제에서 A를 오름차순으로 정렬하면 0 1 1 1 6, B를 내림차순으로 정렬하면 8 7 3 2 1 이므로 구하는 합은 0+7+3+2+6=18 이다.
코드:
파이썬에서 내림차순으로 정렬하는 방법, lambda를 쓰는 방법 잘 익혀두자!
#정렬
import sys
n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
A.sort() #오름차순 정렬
B.sort(reverse = True) #내림차순 정렬
ans = 0
for i in range(n):
ans += A[i]*B[i]
print(ans)