[백준 1026 파이썬] 보물 (실버4, 그리디)

알고리즘 유형 : 그리디
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
A = [*map(int, input().split())]
B = [*map(int, input().split())]

A_ascending = sorted(A)
B_descending = list(reversed(sorted(B)))
result = 0

for i in range(N):
    result += A_ascending[i] * B_descending[i]

print(result)

풀이 요약

1. S의 최소값을 구하기 위해선, A에서 작은 값을 B의 큰 값에 매칭하면 된다. B의 큰 값들은 최대한 덜 곱해주는게 최소값을 구하는 메커니즘이 된다.

2. 이를 위해 A를 오름차순, B를 내림차순으로 정렬 후 for 돌면서 곱을 더해주고, 그 값을 출력하자.

배운 점, 어려웠던 점

• 쉬운 그리디 문제였다.