[파이썬] 백준 1026 : 보물

[파이썬] 백준 1026 : 보물

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

1026번: 보물

실버 4 (이게 왜 실버4까지나?)

수학, 그리디 알고리즘, 정렬

---

접근

곱하기를 할때 가장 작은 값이 나오려면 작은 수는 큰 수와 서로 곱하도록 하면 된다.

그냥 단순하게 A는 오름차순, B는 내림차순해서 서로 곱하면 좋겠지만 B는 재배열 하지 말랬으니 B의 최댓값을 계속해서 갱신하는 방법으로 문제를 풀었다.

 

코드 풀이

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A.sort()
S = 0
for i in range(N):
    max_i = B.index(max(B))
    S += (A[i] * B[max_i])
    B.remove(B[max_i])
print(S)

 

A를 오름차순 정렬한다.

B는 index함수를 사용해 가장 큰 값에 대한 인덱스 번호를 찾아낸다.

A의 i번째 원소의 값과 곱하고 S에 그 값을 더해준다.

그리고 가장 큰 값을 B에서 지운다.

 

A, B의 원소 개수가 같으므로 별 어려움없이 풀이가 가능하다.