문제
강의에 들어있는 문제라서 문제 링크를 걸어도 되는지 모르겠다.
길이가 같은 배열 A, B가 있다.
A, B 배열에서 각각 한 개의 숫자를 뽑아 두 수를 곱하는 과정을 길이만큼 반복하며,
곱한 값을 누적하여 더한다. (중복으로 뽑을 수는 없다)
이때 최종적으로 누적된 값이 최소가 되도록 하자.
A, B의 크기 : 1000이하의 자연수
A, B의 원소의 크기 : 1000이하의 자연수
입출력 예시
| A | B | return |
|---|---|---|
| [1, 4, 2] | [5, 4, 4] | 29 |
| [1, 2] | [3, 4] | 10 |
접근
직관적으로 봤을 때, 가장 작은 수와 가장 큰 수를 곱한다면 전체 합이 가장 작다는 건 알겠다.
\[A = {a_1, a_2, ..., a_n}\] \[B = {b_1, b_2, ..., b_n}\] \[a_1 < a_2 < ... < a_n\] \[b_1 > b_2 > ... > b_n\]인 경우,
\[\sum_{n=1}^{n} a_n * b_n\]이 항상 최소라는 사실을 어떻게 증명할 수 있을까?
누가 알려줬음 좋겠다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
def solution(A,B):
A.sort()
B.sort(reverse = True)
answer = 0
for i in range(len(A)):
answer = answer + A[i]*B[i]
return answer