[백준 알고리즘: python 3] #1026 - 보물

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

 

1026번 문제는 보물이라는 이름으로 소개되어 있습니다. 어렵지 않은 문제였고, 다만 저는 문제를 풀 때 두가지 방법이 생각이 났었네요.

 

 

Hint!

이 문제에서 주어진 것처럼, A는 재정렬을 해야하는 수열, B는 그대로 있어야 하는 수열입니다. S는 두 배열의 각 원소끼리 곱하여 더하는 수식을 의미합니다. (임의로 배열을 설정하고 수식에 적용하시면 알 수 있습니다.) 두 배열의 각 원소끼리 곱하여 더했을 때, 최소가 되는 상황은 한 원소가 크면 클수록 곱해지는 다른 원소는 작아져야 한다는 것입니다. 문제의 예제와 힌트를 보면, 재정렬된 A는 B의 원소들 중 가장 큰 원소 (8)를 A 원소들 중, 가장 작은 수(0)와 매치하고 그 다음 큰 수는 그 다음 작은 수로 재정렬된 것을 볼 수 있습니다.

 

그러면, B의 원소들을 재정렬했을 때 인덱스들을 저장해서 A를 재정렬하고, 최소가 되는 S값을 구해야할까요? 재정렬된 A를 요구하는 문제였다면 그렇게 했어야 하지만, 계산된 S를 구하는 것이기 때문에 그러지 않아도 됩니다. 그냥 A는 오름차순 정렬, B는 내림차순 정렬(A와 역순으로 정렬)하여 각 원소끼리 곱해주면 됩니다! 그럼 우리가 의도한 계산 방식과 같아지게 됩니다.

 

아래의 코드로 성공하였습니다.

import sys

N = int(sys.stdin.readline())
A = sorted(list(map(int, sys.stdin.readline().split()))) # 오름차순 정렬
B = sorted(list(map(int, sys.stdin.readline().split())))[::-1] # 내림차순 정렬

S = 0
for a, b in zip(A, B): S += a * b
print(S)