16208번. 귀찮음

 

아이디어

a1 + ... + an = S 라고 할 때 이를 두 개의 막대로 자르면 K, S - K 인 막대가 되며 이 때의 비용은 K(S-K) 이다.

 

K 를 어떻게 결정할 것인지의 문제이므로 이를 K 에 대한 2차 함수라고 생각하면 계수가 음수이므로 K 가 최소 또는 최대가 될 때 비용 또한 최소가 된다.

 

이는 곧 두 개의 막대로 자를 때 최소한의 비용을 사용하는 방법은 a1 ~ an 중 가장 작은 막대의 길이만큼 자르는 것이라는 의미이다.(더 작게 자르면 현우가 원하는 막대를 모두 만들 수 없음)

 

따라서 a1 ~ an 이 오름차순 정렬됐다고 가정할 때 a1 * (a2 + ... + an) 이 막대를 둘로 자르는 최소 비용이 되는 것이다.

 

한 번 막대를 잘라서 a1 을 얻었다면 (a2 + ...  + an)에 대해서 a2 * (a3 + ... + an) 으로 자르고, 그 이후 과정을 반복해서 an 까지 얻으면 이를 종료하여 그동안의 비용을 합산하면 문제에서 원하는 답을 얻을 수 있다.

 

 

풀이코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] needs = new int[n];
        int totalLength = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            needs[i] = Integer.parseInt(st.nextToken());
            totalLength += needs[i];
        }

        Arrays.sort(needs);

        long result = 0;
        for (int i = 0; i < n - 1; i++) {
            totalLength -= needs[i];
            result += ((long) needs[i] * totalLength);
        }

        System.out.println(result);
    }
}