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

June·2021년 3월 11일
1

알고리즘

목록 보기
138/260

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

내 풀이

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

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

A=a1,a2,...,anB=b1,b2,...,bna1<a2<...<anb1>b2>...>bnA = 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 \\
ai<aj(1<=i<j<=n)bx>by(1<=x<y<=n)a_i < a_ j (1<= i < j <=n)\\ b_x > b_y (1 <= x < y <=n)\\

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

aibm+ajbna_ib_m + a_jb_n\\

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

aibn+ajbma_ib_n + a_jb_m

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

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

aibx+ajby>aiby+ajbxai(bxby)>aj(bxby)ai>aj\\ a_ib_x + a_jb_y > a_ib_y +a_jb_x\\ a_i(b_x - b_y) > a_j(b_x-b_y) \\ a_i > a_j
참고:bx>by이므로bxby>0이다참고: \\ b_x > b_y 이므로\\ b_x - b_y > 0이다

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

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

1개의 댓글

comment-user-thumbnail
2021년 9월 3일

배우고 갑니다. 감사합니다.
'b_x > b_y (1 <= x < y <= n)' 이 부분에서
'b_x > b_y' 이 부분을
'b_x < b_y' 으로 수정해야 되는 건가요?

답글 달기