[파이썬] 백준 알고리즘 1026 : 보물, python

문제 : 보물

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

---

문제 풀이

문제를 보면 A[N]과 B[N]의 곱을 통하여 가장 작은 값을 만들면 되는 알고리즘이다.

문제에 힌트가 있다. 즉, A는 재배열이 가능하며, B는 재배열이 안된다. 각각 배열의 최댓값과 최솟값의 곱을 더한 값이 문제에서 원하는 답인 최솟값이다.

N = int(input())

Alist = list(map(int, input().split()))
Blist = list(map(int, input().split()))

temp = 0

for _ in range(len(Alist)):
    temp += min(Alist)*max(Blist)
    Alist.remove(min(Alist))
    Blist.remove(max(Blist))

print(temp)

위 코드를 보면, 주어진 각각의 값을 리스트에 넣고, 그 값의 최솟값과 최댓값을 곱하여 temp에 더하게 된다.

그 뒤 사용한 값(min/max)은 다음 계산을 위해 제거(remove)를 한다.