[Python] 백준 풀기 1026 - 보물

파이썬 백준 1026번

실버4

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

1026번: 보물

 

 

 

 

 

문제 보기

분류: 수학, 그리디 알고리즘, 정렬

 

 

 

 

 

문제 풀기

문제의 의도가 좀 애매한 것 같다.

B를 정렬하지 말라고 했는데 정작 결과를 도출해야 하는 요소는 주어진 계산식으로 만들어질 수 있는 최솟값이다.

따라서, S = A[0] × B[0] + ... + A[N-1] × B[N-1] 에서 B 의 배열은 마음속에 고정해 두고, A 와 B 가 짝을 이룰 수 있는 방법을 생각하며 최솟값을 구한다.

 

 

접근 방법은 어렵지 않다. A 에서 가장 작은 값과 B 에서 가장 큰 값을 곱하고, 그다음 A의 두 번째 작은 값과 B 의 두번째 큰 값을 곱하고, 그다음... 이 규칙 수행을 N 번 한다.

매 회 실행할 때마다 그 값을 누적 합하여 변수 total_sum 에 저장한다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline


def fnMinimumS():
    A_ls.sort(reverse = False)
    B_ls.sort(reverse = True)
    print(A_ls)
    total_sum = 0
    for i in range(N):
        total_sum += A_ls[i] * B_ls[i]
    
    return total_sum


if __name__ == "__main__":
    N = int(inputdata().strip())
    A_ls = list(map(int, inputdata().split()))
    B_ls = list(map(int, inputdata().split()))
    
    result = fnMinimumS()
    
    print(result)