[BOJ] 1026번 | 보물 (Python3)

🔗문제 보러가기

1026번: 보물

 

 

문제 설명

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

 

$$ S = A[0] \times B[0] + ... + A[N-1] \times B[N-1] $$

 

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.

 

---

입력

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

 

---

출력

첫째 줄에 S의 최솟값을 출력한다.

 

---

예제 입출력

 

---

풀이 전략

단순히 수학적으로 생각하면 작은 수와 큰 수끼리 곱하는 게 최솟값이 될 테니 어렵진 않은데, B 배열을 재배열할 수 없다는 패널티가 있었습니다. 어떻게 해결할까 고민하다가 메모리 좀 쓰고 해결하자는 생각으로 풀었습니다.

1. A 배열을 내림차순 정렬한다. (오름차순으로 하고 싶다면 그렇게 해도 됩니다.)
2. for 문을 통해 A 배열의 원소를 하나 가져오고, 이 때 B 배열의 가장 작은 수의 인덱스 번호를 찾는다.
3. A 배열을 복사한 새로운 배열의 해당 인덱스 위치에 for문을 통해 가져온 A 배열 원소를 집어 넣는다.
4. 처리 완료된 B의 원소는 이후 탐색에서 제외되도록 무한대로 처리한다.
5. for 문을 다 돌 때까지 2-4번 과정을 반복한다.
6. for 문을 다 돌았다면, 처리한 A와 B의 각 원소를 곱해 전체 합계를 낸다. 

 

---

소스 코드 및 결과

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

A.sort(reverse = True)
tempB = B.copy()
resultA = A.copy()

for elementA in A:
    minElementB = min(tempB)
    idx = tempB.index(minElementB)
    resultA[idx] = elementA
    tempB[idx] = float("inf")
    
del tempB
minSum = 0
for a, b in zip(resultA, B):
    minSum += a * b

print(minSum)