[백준/c++] BOJ 16208 - 귀찮음

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

16208번: 귀찮음

 

 

문제 설명

길이 a1, a2, ..., an의 총 n개의 쇠막대가 필요하다. 현재는 a1 + a2 + ... + an 길이의 하나의 쇠막대만 가지고 있다.

이 막대를 직접 잘라 원래 필요하던 n개의 쇠막대를 만들 것이다.

길이 x + y인 막대를 길이 x, y인 두 개의 막대로 자를 떄는 만들려고 하는 두 막대의 길이의 곱인 x*y의 비용이 든다.

최소한의 비용으로 쇠막대를 잘라 n개의 쇠막대를 만든다고 할 때, 필요한 최소 비용을 구한다.

쇠막대의 수 n ( 1 <= n <= 500,000 )

쇠막대의 길이 ai ( 1 <= ai <= 101 )

해결

간단한 그리디 문제이다.

 

n이 4 이고, ai는 각각 3, 5, 4, 2라고 가정해 보자.

그럼 현재 가진 쇠막대의 길이는 3 + 5 + 4 + 2 = 14일 것이다.

처음 막대를 자를 때 드는 비용을 각각 계산해 보면

2 ->2 * 12 = 23

3 -> 3 * 11 = 33

4 -> 4 * 10 = 40

5 -> 5 * 9 = 45

 

이렇게 얻으려는 막대의 길이가 짧을수록 더 적은 비용으로 자를 수 있다는 것을 알 수 있다.

 

따라서 작은 막대부터 큰 막대까지 순서대로 얻어 주면 된다.

 

얻으려는 막대 ai를 n번 벡터 v에 받아 정렬해 주었다.

v의 idx 순서대로 돌며 비용을 계산해 주었다. (작은 길이의 막대부터 비용을 계산)

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

long long n, sum = 0, ans = 0;
vector<long long> v;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v.push_back(a);
		sum += a;
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		ans += v[i] * (sum - v[i]);
		sum -= v[i];
	}

	cout << ans;
}