[백준, BOJ 10427] 빚 (java)

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

10427번: 빚

728x90

---

메모리: 15,580 KB , 시간: 228 ms

사용 알고리즘: 그리디 알고리즘, 누적 합, 정렬

 

내 생각

이 문제 설명이 좀... 이해가 잘 안되게 써둔 느낌...!

그래서 위의 설명은 안보고 공식만 봤다.

 

배열에서 M개를 선택했을 때,

선택한 M개 중 가장 큰 수를 a라고 한다면

a * M - (선택한 M개 수들의 합)의 최솟값이 S(M)이다.

 

답은 S(1), S(2), ..., S(N)을 모두 합하면 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static long[] A;
    static long[] sumA;

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder answer = new StringBuilder();

        // T := 테스트케이스의 수
        int T = Integer.parseInt(br.readLine());

        long result;
        for (int tc = 0; tc < T; tc++) {
            // N := 돈 빌린 횟수, A[i] := i번째에 빌린 돈 액수
            st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            A = new long[N];

            for (int i = 0; i < N; i++) {
                A[i] = Long.parseLong(st.nextToken());
            }

            // A 올림차순으로 정렬
            Arrays.sort(A);

            // A의 누적합 구하기
            sumA = new long[N];
            sumA[0] = A[0];
            for (int i = 1; i < N; i++) {
                sumA[i] = sumA[i - 1] + A[i];
            }

            // S(i) 구하기
            result = 0;
            for (int i = 2; i <= N; i++) { // S(1)은 무조건 0이기 때문에 넘어감
                result += getS(i);
            }

            answer.append(result + "\n");
        }

        System.out.println(answer);
    }

    private static long getS(int i) { // S[i] 구해주는 함수

        /**
         *  A에서 i개를 골라야 함.
         *
         *  고른 i개 중 가장 큰 수(a)를 제외한 나머지 (i - 1)개의 수는
         *  a보다 같거나 작은 수 중 가장 큰 것들로 골라야 함
         */

        long ret = Long.MAX_VALUE;

        long tmp;
        for (int j = i - 1; j < N; j++) {
            tmp = A[j] * i - (sumA[j] - (j - i > -1 ? sumA[j - i] : 0));
            ret = Math.min(ret, tmp);
        }

        return ret;
    }
}