[백준/1026/파이썬] 보물

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

1026번: 보물

Problem

• 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
• 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
• S = A[0] × B[0] + ... + A[N-1] × B[N-1]
• S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자.

조건

• B에 있는 수는 재배열하면 안 된다.
• 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

SOL

완전탐색을 하려면, N! (모든 경우)의 수를 봐야하므로, 완전탐색으로 할 시에는 불가능하다.

두 배열의 곱이 최소가 되려면, 최솟값 *최댓값 + 두번째 최솟값 * 두번째 최댓값 ..... 이렇게 하는게 맞다.

하지만, B의 배열은 재배열하면 안되니까, 생각을 좀 해봐야하는 방법이다.

 

흠. 재배열만 해주면 안되니까.. B를 건드려도 되나? B가 사라져도 된다면, Max값을 pop해주기만 하면 되는 문제이다.

혹시나 싶어서, 제출을 해보니까 맞았다! B를 훼손시켜도 되나보다.

 

#보물

N= int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
S=0
for i in range(N):
    S += min(A)*max(B)
    A.pop(A.index(min(A)))
    B.pop(B.index(max(B)))

print(S)