[백준] 10427 빚

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

 

그리디 + 누적합 문제인데

 

쉽게 말해서 M = 3 이면 3 * [고른 3개 숫자 중에서 제일 큰 값 ] - [고른 3개의 숫자 총합] 인 값들의 집합 중에서 제일 작은 값들의 합이 얼마인지 찾는 문제이다.

 

지문을 보고 내가 알고 있는 형태로 바꾸는 연습을 계속 해야 한다.

 

일단 딱봐도 10^4개 중에서 1개 고르고, 2개 고르고 ... N 개 고르는 건 완전 탐색으론 절대 무리기 때문에 정렬을 통한 그리디를 생각 해볼 수 있다.

 

정렬을 해보면 예를 들어서 [3, 5, 10, 14, 17] 이 있다고 가정해 보자. 처음 1개를 고르는 S(1) 은 어차피 0 이므로 제외하고 S(2)일 때를 가정하면 

 

2 * 5 - (3 +5)

2 * 10 - (5 + 10)

...

이런 형태가 나온다.

 

S(3)일 때도 생각 해보면

 

3 * 10 - (3 + 5 + 10) 

3 * 14 - (5 + 10 + 14)

...

이런 식이다. 그렇다면 S(2)와 S(3)는 사실 독립된 상황이기 때문에 S(2)에서 뭘 고르든 S(3)에 영향을 미치지 않는다.

그리고 S(2)의 최적의 조건을 알면 각 S(N)의 최적이 전체 구하려는 합의 최적임이 증명된다.

그렇기 때문에 그리디를 적용할 수 있고, 이를 계산할 때 연속된 배열의 합이 필요하기 때문에 누적합으로 시간초과를 피하는 것이다.

def solution(n,A):

    A.sort()

    ans = 0

    s = list.copy(A)

    s.pop()

    for i in range(2,n):

        tmp = 999_999_999

        for j in range(i-2,n-1):

           s[j- (i-2)] += A[j+1]

           #print(i,A[j+1], s[j - (i-2)], A[j+1])

           p = i * A[j+1] - s[j - (i-2)]

           tmp = min(tmp,p)

       

        ans += tmp

    ans += n * A[n-1] - sum(A)

    print(ans)

T = int(input())

for _ in range(T):

    A = list(map(int,input().split()))

    solution(A[0], A[1:])

 

그리고 마지막 S(N)은 어차피 전체 리스트의 합에 제일 큰 값을 곱한 것의 차 이므로 마지막에 처리를 해주면 된다.