[알고리즘] 프로그래머스 - 최솟값 만들기

프로그래머스 - 최솟값 만들기

내 풀이

def solution(A,B):
    A.sort()
    B.sort(reverse = True)
    answer = 0
    for i in range(len(A)):
        answer += A[i] * B[i]
    return answer

직관적으로 서로 다르게 정렬해 큰 것과 작은 것을 곱하는 방식을 생각했다. 문제를 푼 이후에 증명을 간단하게 해봤다.

i와 j 그리고 x와 y를 1이상 n 이하의 임의의 수라고 하자.

위의 표현은 큰것과 작은 것끼리 곱하는 방식이다.

위의 표현은 작은 것끼리 곱하는 방식이다.

만약 큰수와 작은수끼리 곱한 방법이 큰수와 큰수 그리고 작은 수와 작은 수 끼리 곱한 것보다 크다고 가정해보자.

참고는 귀류법에서 두 번째 줄에서 b_x-b_y로 양변을 나눠도 부등호 방향이 바뀌지 않는 이유이다. a_i > a_j는 우리가 가정한 a_i < a_j와 모순이 된다. 따라서 귀류법으로 큰수와 작은수끼리 곱한 방법은 작은수와 작은수끼리 곱한 것보다 크지 않다.

코드에서 풀었던 오름차순으로 정렬하고, 내림차순으로 정렬해서 푸는 방법이 아닌 방법으로 풀면 작은수와 큰 수끼리 곱하지 않는 부분은 1개 이상 생긴다. 따라서 최소값이 될 수 없다.