백준 10427 빚 / python

문제 : 10427

풀이 point

어떤 한 숫자 A를 선택했을 때 A보다 작은 숫자 M-1개를 골라 그 합과 AxN를 뺀 값이 가장 최소가 되도록 해야한다. 물론 완전탐색은 시간 초과이기 때문에 누적합과 정렬을 이용하여 시간을 단축할 수 있다.

풀이 방법

먼저 입력받은 빚의 값들을 정렬해준다. 정렬하는 이유는 A보다 작은 숫자 M-1개를 고를 때 편하기 때문이다. 만약 정렬이 안되어 있다면 작은 숫자를 일일이 찾아야하지만, 정렬 되어 있다면 A기준 왼쪽에 몰려 있다. 그리고 누적합을 구하기 위해 필요하다.

그 다음 빚의 누적합을 구한다. 누적합을 구하게 되면 숫자 M-1개를 골라 그 합을 구하는 것까지는 완료하였다.

이제는 AxN값에서 그 합을 뺀 값이 가장 최소가 되는 부분만 구하면 된다. 리스트에 맨 처음부터 A위치까지 for문을 진행한다. 누적합을 구한 후 가장 최소가 되는 비용을 구하면 된다.

이 과정을 2, N까지 반복한다.(1은 무조건 0임)

코드

import sys
input = sys.stdin.readline

for i in range(int(input().rstrip())):
    N, *light = map(int, input().split())

    light.sort()
    sumLight = [0]*(N+1)

    for i in range(N):
        sumLight[i+1] = sumLight[i] + light[i]

    ans = 0

    for i in range(2, len(light)+1):
        minCost = float('inf')
        for j in range(N-i+1):
            preSum = sumLight[j+i] - sumLight[j]
            maxNum = light[j+i-1]
            cost = maxNum * i - preSum
            minCost = min(cost, minCost)
        ans += minCost

    print(ans)