백준 10427 빚 Kotlin (누적 합)

문제 출처 : https://www.acmicpc.net/problem/10427

10427번: 빚

문제

민균이에게는 ‘빚쟁이’ 라는 별명이 있다. 이 별명은 악덕 사채업을 하는 김우현연구소에서 민균이가 빌린돈을 잘 갚지 않는다고 하여 붙여준 이름이다. 

민균이가 최근 N (1 ≤ N ≤ 4000) 번 돈을 빌렸고, 그때마다 빌린 돈이 각각 A(1), A(2), …, A(N) (1 ≤ A(i) ≤ 104) 라고 하자. 악덕 사채업소 김우현 연구소는 이름만큼이나 빌린 돈을 갚는 방식이 독특하다.

먼저, 김우현 연구소가 민균이에게 M번 (1 ≤ M ≤ N) 의 빚을 갚으라고 명령하면, 민균이는 N번중 아무렇게나 M 번을 고르고, 고른 것 중에서 가장 많은 돈을 빌렸을 때 빌린돈 x M 을 갚아야 한다. 이렇게 하면 민균이가 김우현 연구소에 갚아야 하는 돈은 (빌린돈 + 추가적으로 더 갚아야 할 돈) 이 된다. 예를 들어, 민균이가 3번 돈을 빌렸고, 각각 2, 5, 3 의 돈을 빌린 경우, 김우현 연구소가 2번의 빚을 갚으라고 명령하면, 민균이가 첫 번째, 두 번째를 선택했을 경우 갚아야 하는 돈은 5 x 2 = 10 이 되고, 추가적으로 더 갚아야 할 돈은 10 – (2 + 5) = 3 이 된다. 만약 민균이가 첫 번째, 세 번째를 선택하면, 갚아야 하는 돈은 3 x 2 = 6 이 되고, 추가적으로 더 갚아야 할 돈은 6 – (2 + 3) = 1 이 된다. 

민균이는 이런 김우현 연구소가 괘씸하여 어떻게든 추가적으로 더 갚아야 할 돈을 최소한으로 하고 싶어 한다. S(M) 을 김우현 연구소가 민균이에게 M번의 빚을 갚으라고 명령했을 때 민균이가 M 번을 선택하여 추가적으로 갚아야 하는 돈의 최솟값이라고 하자.

예를 들어 N = 5 이고, 민균이가 N번동안 빌린 돈이 A = {1, 5, 4, 3, 8} 인 경우, 

• S(1) = 0 (어떻게 선택해도 추가적으로 갚을 돈은 없음)
• S(2) = 1 (2, 3일 분을 갚거나 3, 4일분을 갚는 경우 추가적으로 1을 더 갚으면 됨)
• S(3) = 3 (2, 3, 4 일분을 갚는 경우 추가적으로 3을 더 갚으면 됨)
• S(4) = 7 (1, 2, 3, 4일분을 갚는 경우 추가적으로 7을 더 갚으면 됨)
• S(5) = 19 (1, 2, 3, 4, 5일분을 갚는 경우 추가적으로 19를 더 갚아야 됨)

이제 여러분이 할 일은 민균이가 돈을 빌린 횟수 N 과 N번동안 각각 빌린 돈 A(1), A(2), …, A(N)이 주어졌을 때, S(i) 의 합 S(1), S(2), …, S(N)을 구하는 것이다.

입력

먼저 테스트케이스의 수 T가 주어지고 이어져서 각각의 줄에 N과 A(i)의 정보가 차례대로 주어진다.

출력

각각의 줄에 대해 S(1) + … + S(N) 을 구한다. 중간 과정 및 답은 int 범위를 초과할 수 있으므로, 64bit 정수형(long long: C/C++, long: Java) 를 이용해야 한다. 입출력은 

C/C++: printf("%lld\n",answer);
Java : System.out.println(answer);

로 할 수 있다.

알고리즘 분류

• 그리디 알고리즘
• 정렬
• 누적 합

풀이

누적 합 문제이다.

우선 문제를 정리하면,

1, 5, 4, 3, 8이란 입력에 M이 3인 경우 무작위로 3개를 선택해야 한다.

만약 5,4,8을 선택했다고 하면

f(M) = 8*3 - (5+4+8) = 7

즉, 선택한 m개 중 가장 큰 값 * M에다가 선택한 값들의 합을 빼면 된다.

이렇게 구한 f(M)중 가장 작은 값이 S(M)이 되는 거고, S(1~N)을 구하면 된다.

우리가 필요한 값은 M개의 값 중에 가장 큰 값과 M개의 수의 합이다.

 

1,5,4,3,8 에서 만약 M개를 선택했을 때 가장 큰 값이 5라고 해보자.

그럼 5와 같이 선택할 수 있는 값들은 1, 4, 3이다.

이렇게 5보다 작은 값들이 산개되어있으므로 우리는 매번 5보다 작은 값들을 배열 전체를 순회하며 찾아내야 한다.

하지만 이를 정렬한다면?

1, 3, 4, 5, 8로 내가 최댓값으로 선택한 값보다 작은 값들이 왼쪽에 존재하게 된다.

여기서 5를 최댓값으로할 때 S(2)를 구해보자. // 2개를 선택

5를 최댓값으로 했으니 가능한 f(2)는 

(1,5) = 5*2 - (5+1)

(3,5) = 5*2 - (5+3)

(4,5) = 5*2 - (5+4)

즉 5를 최댓값으로 할 때 S(2) = (4,5) = 1이 된다.

여기서 알 수 있는 것은 정렬된 배열에서 S(M)을 구하려면 최댓값 인덱스 i를 설정하고, i부터 차례로 M개를 포함시키면 된다.

 

조금 더 설명하면,

8이 최댓값이라 할 때 M이 4라고 해보자.

(1, 3, 4, 8) 을 선택하는 것과 (3, 4, 5, 8)을 선택하는 것 무엇이 더 작은 값을 얻을 수 있을까?

최댓값 * M  - (M개의 합)이기 때문에 M개는 최대한 큰 숫자들로 채우는 것이 좋다.

다만, M이 4라고 하면 8을 최댓값으로 하는 것보다 무조건 5를 최댓값으로 하는 것이 유리하겠죵?

 

무튼 설정할 최댓값은 정렬된 리스트로 구할 수 있고, 이에 대한 누적 합을 만들어 설정한 최댓값의 인덱스 i 부터 i-m+1의 합을 구하면 된다.

 ex) M이 3인 경우 탐색 시작 부분

기존 리스트(정렬됨)

index	0	1	2	3	4
value	1	3	4	5	8

 누적 합

index	0	1	2	3	4	5
value	0	1	4	8	13	21

누적 합과 기존 리스트의 인덱스는 맞춰줘도 상관없고 본인은 누적 합은 1부터, 기존 리스트는 0부터로 했다.

점화 식은 다음과 같다.

origin[2] * 3 + (preSum[3]-preSum[0])

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()


fun main() = with(System.out.bufferedWriter()){

    repeat(getInt()){
        getIntList().apply {
            val n = this[0]
            val origin = List(this.size-1){this[it+1].toLong()}.sorted()
            val preSum = LongArray(this.size)
            for(i in 1 until preSum.size){
                preSum[i] = preSum[i-1] + origin[i-1]
            }
            var answer = 0L
            for(m in 2 .. n){
                var min = Long.MAX_VALUE
                for(i in 0 .. n-m){
                    min = min.coerceAtMost(origin[i+m-1]*m - (preSum[i+m]-preSum[i]))
                }
                answer += min
            }
            write("$answer\n")
        }
    }

    close()
}