[BOJ] 백준 16208번 : 귀찮음 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/16208

16208번: 귀찮음

문제

현우는 무슨 이유에선지 길이 a1, ..., an의, 총 n개의 쇠막대가 필요해졌다. 하지만 그가 가진 것은 길이 a1+...+an의 하나의 쇠막대뿐이었다. 현우는 이 막대를 직접 잘라서 원래 필요하던 n개의 쇠막대를 만들 것이다. 길이 x+y인 막대를 길이 x, y인 두 개의 막대로 자를 때에는 만들려 하는 두 막대의 길이의 곱인 xy의 비용이 든다. 현우는 최소의 비용으로 이 쇠막대를 잘라서 a1, ..., an의 n개의 쇠막대를 얻고 싶다.

그런데 현우는 이 비용이 얼마나 들지 잘 모르겠다. 그래서 여러분이 막대를 자르는 최소 비용을 계산하는 프로그램을 작성해주면 코드잼 경시대회 점수를 30점 올려주겠다고 제안했다. 어떤가?

 

입력

첫째 줄에는 현우가 원하는 쇠막대의 수를 나타내는 정수 n이 주어진다. (1 ≤ n ≤ 500,000)

둘째 줄에는 현우가 원하는 쇠막대의 길이를 나타내는 정수 a1, ..., an이 주어진다. (1 ≤ ai ≤ 101)

 

출력

현우가 필요한 n개의 쇠막대를 얻는 최소의 비용을 출력한다.

 

 

풀이

수학적인 지식만 사용하면 되는 문제였습니다.

풀이를 시작하기에 앞서, N = 4이고 a1 = 3, a2 = 5, a3 = 4, a4 = 2를 예시로 들겠습니다.

현재, 현우가 가지고 있는 쇠막대기 길이는 3 + 5 + 4 + 2 = 14이고, 우리는 3, 5, 4, 2 각각의 쇠막대기를

얻어내는 것이 목표입니다.

그리고 쇠막대기를 2개로 분할할 때마다 그 2개의 길이를 곱해야 합니다. 가령, 14인 쇠막대기에서 3을 얻어내고 싶다면,

3 * (14 - 3) 를 함으로써, 쇠막대기의 길이는 11로 줄고 사용 비용은 3 * 11 = 33이 되는 것입니다.

그리고 쇠막대기를 어떻게 자르든 비용은 모두 같기때문에 각각에 대해서 위 작업을 수행하면 됩니다.

 

증명

잘라야하는 쇠막대기의 길이를 a1, a2, a3라 하고, 현재 가지고 있는 쇠막대기의 길이를 X라 하자.

여기서 X는 a1 + a2 + a3를 한 값이다. 이 상태에서 비용을 구하는 식은 다음과 같다.

a1 * (X - a1) + a2 * (X - a1 - a2) + a3 * (X - a1 - a2 - a3) = a1 * (a2 + a3) + a2 * a3 + a3  * 0

= a1a2 + a1a3 + a2a3 이다. 그리고 최종 정리된 'a1a2 + a1a3 + a2a3'를 유심히 살펴보자.

3가지 막대가 서로 각각을 곱했다는 사실을 알 수 있다. 위 식을 n으로 확장하면

a1a2...an + a1a3...an + ... + an-1an이 될 것이기때문에 어느 순서로 자르든 비용은 모두 같게 된다는 사실을

어렵지 않게 알 수 있다. 

 

소스 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine()); // 필요한 쇠막대기의 수
 
        long[] arr = new long[N]; // 필요한 쇠막대기 배열.
        long total = 0; // 현우가 가지고 있는 쇠막대기의 길이(arr 배열의 모든 요소의 합)
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(st.nextToken());
            total += arr[i];
        }
 
        long ans = 0;
 
        // 연속해서 쇠막대를 2개로 분리하고, 그 2개의 곱을 구하는 과정.
        for (int i = 0; i < N; i++) {
            long temp = arr[i];
            total -= temp;
            ans += temp * total;
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

느낀 점

사실, 증명에서의 식에서 볼 수 있듯이 2중 반복문으로 구현하여 비용을 구할 수도 있습니다. 하지만, 이것은 O(N^2)을 

요구하기때문에 적절하지 않으며, 문제에서 나와있는 대로 전체 길이를 구하고, 하나씩 빼면서 곱해야 O(N)으로 통과가 

가능했습니다. 여기서 한 가지 더 알 수 있는 것은 전체 길이를 구하고 하나씩 빼면서 곱하는 방식은 일종의 최적화 방식

이었다는 것입니다!

즉, '1쌍씩 각각의 요소를 곱하여 더한 값을 구하여라'라는 문제는 '모든 요소의 합을 구하고 그 합에서 어떤 요소의 길이

를 빼고 그 요소를 곱하면서 더하여라.'와 동치가 되는 것입니다. 이것은 O(N^2) -> O(N)으로 바꾸는 귀중한 기법이기

때문에 잘 기억해 두어야겠다고 생각했습니다!

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.