[BOJ] 1026. 보물

문제

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

1026번: 보물

 

 

---

 

주요 아이디어

전체 합을 최소값으로 만들려면, (현재 A배열의 최대값) * (현재 B배열의 최소값) 을 하나씩 더해주면 된다.

 

---

 

코드 구현 (Python 3)

간단하게 풀려면, A를 오름차순 / B를 내림차순 해서 곱한 후 하나씩 더해주면 된다.

 

n = int(input())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort(reverse=True)

s = 0
for i in range(len(a)):
    s += a[i] * b[i]

print(s)

 

 

---

 

실패 원인

 

하지만 이 풀이는 중요한 것을 놓치고 있다..

바로 문제에서 B는 재배열하면 안된다는 제약 조건을 걸어두었기 때문이다.

따라서 정답 처리는 되지만, 엄밀히 따지면 틀린 풀이이다.

 

---

 

코드 재구현 (Python 3)

따라서 배열 자체를 직접 정렬하는 것이 아니라, A의 최소값 * B의 최대값을 하나씩 배열에서 pop해주는 방식으로 접근해야 한다.

n = int(input())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

s = 0

while a:
    s += a.pop(a.index(min(a))) * b.pop(b.index(max(b)))    

print(s)

 

 

---

 

제출 결과