[백준/그리디] 1026: 보물 - 파이썬

문제

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

1026번: 보물

문제에서 A배열과 B배열의 값들을 곱해서 최솟값을 구하고자 한다.

 

가장 작은 수를 뽑아내려면?

최대값 X 최솟값 + 최대값 X 최솟값 + .... + 최대값 X 최솟값

이렇게 반복하면 된다.

즉 배열 하나는 오름차순 나머지 배열 하나는 내림차순하여 같은 인덱스마다 값들을 곱하면 구하고자 하는 가장작은S값을 얻을 수 있다.

문제를 살펴보면 "단, B에 있는 수는 재배열하면 안 된다." 라는 조건이 붙어있다.

 

그렇다면...

B에 최소값을 한개씩 뽑고 A에 최대값을 한개씩 뽑아서 두 값을 곱하고 뽑은 두 값은 버린다음

새로 뽑아서 곱하고..

이 곱한값들을 다 더하면 S를 구할 수 있다.

 

아니 이러면 "단, B에 있는 수는 재배열하면 안 된다." 라는 제약조건을 왜 걸어둔걸까..?

잘 모르겠다..

 

답으로 인정되지만 문제 조건을 위반한 풀이

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a.sort(reverse=True)
b.sort()
answer = 0
for i in range(n):
    temp = a[i] * b[i]
    answer += temp
    
print(answer)

 

문제 조건을 만족한 풀이

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
answer = 0
for i in range(n):
    a_max = a.pop(a.index(max(a)))
    b_min = b.pop(b.index(min(b)))
    answer += (a_max*b_min)
print(answer)