[BOJ/Silver 1] 백준 16208 귀찮음(Java)

문제 링크

https://www.acmicpc.net/problem/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개의 쇠막대를 얻는 최소의 비용을 출력한다.

 

서브태스크 1 (4점)

n = 4를 만족한다.

 

서브태스크 2 (14점)

1 ≤ n ≤ 5,000을 만족한다.

 

서브태스크 3 (12점)

문제에 제시된 조건 외의 다른 제약은 없다.

 

예제 입력 1

4
3 5 4 2

예제 출력 1

71

예제 입력 2

10
12 43 22 51 2 55 8 21 98 50

예제 출력 2

55164

 

알고리즘 분류

• 그리디 알고리즘

 

풀이

막대의 길이를 L이라고 하고, 총 N가지의 막대 a1, a2, ..., aN으로 자르고 싶다고 하자.

이를 순서대로 자르면 필요한 비용은 a1 * (L - a1) + a2 * (L - a1 - a2) + ... + aN - 1 * (L - a1 - a2 - ... - aN - 1)가 되고, 이는 a1 * (a2 + a3 + ... + aN) + a2 * (a3 + a4 + ... + aN) + ... + aN - 1 * aN이 된다.

이것은 a1부터 aN까지 각각의 막대 2개를 곱한 값의 총합이 되고, 어느 순서로 막대를 자르더라도 같은 비용이 필요하게 된다.

 

코드

import java.io.*;

public class Main {
	
	public static void find_Answer(long Answer) {
		System.out.println(Answer);
	}
	
	public static void settings(int N, String[] A) {
		long Sum = 0;
		
		for (int i = 0; i < N; i++) {
			Sum += Long.parseLong(A[i]);
		}
		
		long Answer = 0;
		
		for (int i = 0; i < (N - 1); i++) {
			Answer += Long.parseLong(A[i]) * (Sum - Long.parseLong(A[i]));
			Sum -= Long.parseLong(A[i]);
		}
		
		find_Answer(Answer);
	}
	
	public static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String[] A = br.readLine().split(" ");
		settings(N, A);
	}

	public static void main(String[] args) throws IOException {
		input();
	}

}