[ BOJ ][JAVA][10427] 빚

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	106	52	48	56.471%

문제

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

민균이가 최근 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

3
5 1 5 4 3 8
3 1 2 3
6 3 4 1 6 8 1

예제 출력 1

30
4
51

접근

처음엔 조합을 사용해서 모든 경우의 수를 뽑아서 계산했는데, TLE가 났다.
시간을 줄이기 위해 고민한 결과
각 배열의 원소의 차이가 적은 구간이 가장 최소값을 뽑아 낼 수 있는 구간임을 찾아내어 쉽게 구현하였다.

코드

/*
    빚
    슬라이딩 윈도우, 규칙찾기, 구현
*/
import java.io.*;
import java.util.*;
public class p10427 {
    static int t, n;
    static int[] arr;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            arr = new int[n + 1];
            visited = new boolean[n + 1];
            for (int i = 1; i <= n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            sb.append(solve()).append("\n");
        }
        System.out.println(sb.toString());
    }
    static long solve() {
        long ret = 0;
        Arrays.sort(arr);
        for (int i = 2; i <= n; i++) {
            ret += func(i);
        }
        return ret;
    }

    // 슬라이딩 윈도우를 이용해 최소값 찾아내기 1 3 4 5 8 
    static long func(int dist) {
        long min = Integer.MAX_VALUE;
        for (int i = 1; i <= n - dist + 1; i++) {
            min = Math.min(min, calc(i, i + dist - 1));
        }
        return min;
    }

    static long calc(int lo, int hi) {
        long ret = 0;
        long big = arr[hi] * (hi - lo + 1);
        long small = 0;
        for (int i = lo; i <= hi; i++) {
            small += arr[i];
        }
        ret = big - small;
        return ret;
    }
}