백준 10427: 빚(python)

문제

 

---

풀이

 

설명을 복잡하게 해 놓아서 푸는 것보다 문제 읽는 게 더 어려웠다. 이래저래 설명해 놓긴 했는데, 요지는

 

빌린 돈들 중 M개를 골랐을 때:

• 기본적으로 갚아야 하는 돈은 M개의 원금(이하 choice 배열이라 하겠음)
• 갚아야 하는 돈은 M * max(choice)
• 따라서, 추가적으로 더 갚아야 하는 돈은 M * max(choice) - sum(choice)

이다.

 

M은 상수, max(choice)는 그 구간의 최댓값이므로 M과 choice를 바꾸지 않는 한 건드릴 방법이 딱히 없다. 따라서 M * max(choice) - sum(choice)을 최소화하려면 sum(choice)를 최대화하는 수밖에 없고, 이 말은 곧 전체 빚 배열에서 max(choice)와 max(choice)보다 작은 것들 중 가장 큰 (M-1)개의 빚을 골라야 함을 뜻한다. 이는 오름차순 정렬된 빚 배열에서 크기가 M인 구간을 통째로 선택하는 것과 동일하므로 아래와 같이 처리한다. 

arr = list(map(int, input().split()))
ordered = sorted(arr[1:])
N = arr[0]

arr은 입력 배열, ordered는 arr에서 빚 배열 부분을 오름차순 정렬한 배열, 빚 개수 N은 arr 첫 번째 원소이다.

 

이후 1부터 N까지 모든 M에 대해 M마다 추가 금액인 additional을 계산하고 S(M)을 누적해야 하며, 앞선 설명 M * max(choice) - sum(choice)에서 max=ordered[i], sum(choice)=psum이다.

res = 0
for M in range(1, N + 1):
    temp = sys.maxsize

    for i in range(M - 1, N):   # ordered[i] 보다 작은 것들 중 (M - 1)개
        psum = sums[i + 1] - sums[i + 1 - M]
        additional = M * ordered[i] - psum

        if additional < temp:
            temp = additional
    res += temp

 

여기서 sums는 구간합 계산을 위한 구간합 배열이다. sums[i]=ordered[0]+ordered[1]+...+ordered[i-1]이므로, 정렬된 배열에서 i-M+1부터 i까지의 합은 sums[i+1]-sums[i+1-M]=psum으로 계산한 것이다.

 

위 과정을 거쳐 가능한 모든 구간에 대해 additional을 구하고, 구간 별 최소 추가 금액을 S(M)으로 선택한다.

---

전체 코드

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    arr = list(map(int, input().split()))
    ordered = sorted(arr[1:])
    N = arr[0]

    sums = [0]
    for i in ordered:
        sums.append(sums[-1] + i)

    res = 0
    for M in range(1, N + 1):
        temp = sys.maxsize

        for i in range(M - 1, N):
            psum = sums[i + 1] - sums[i + 1 - M]
            additional = M * ordered[i] - psum

            if additional < temp:
                temp = additional
        res += temp

    print(res)