문제
https://www.acmicpc.net/problem/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)
제출 결과
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 1463. 1로 만들기 (0) | 2024.04.21 |
---|---|
[BOJ] 12865. 평범한 배낭 (1) | 2024.04.21 |
[BOJ] 14501. 퇴사 (1) | 2024.04.06 |
[BOJ] 14502. 연구소 (0) | 2024.04.06 |
[BOJ] 1260. DFS와 BFS (0) | 2024.04.01 |