문제
현우는 무슨 이유에선지 길이 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개의 쇠막대를 얻는 최소의 비용을 출력한다.
접근 방식
최소 비용을 구하기 위해서는 계속 정렬 상태를 유지하며 작은 값끼리 곱하는 것이 최소 비용을 구할 수 있다고 생각했다
따라서 우선순위 큐를 사용해 최소값 두개를 사용해 최소 비용을 구했다
하지만 만점이 100점이 아니고 30점임을 모르고.. 헤매면서 다른 방법도 찾게 되었다
두번째 방법은 모든 막대 길이를 미리 알아낸 후 각 막대기에 대해 한번에 계산하는 방식이다
즉, 모든 막대 길이를 더하고, 각 막대를 반복문으로 돌면서 현재 막대의 길이와 모든 막대 길이에서 현재 막대의 길이를 곱한 값을 더해주면 최소 비용을 구할 수 있다.
코드
방법 1
#include<bits/stdc++.h>
using namespace std;
int main() {
int n; cin>>n;
vector<int> v(n);
for(int i=0; i<n; i++) cin>>v[i];
sort(v.begin(), v.end());
queue<long long> q;
for(auto c : v) q.push(c);
long long ans = 0;
while(q.size() > 1) {
long long x = q.front(); q.pop();
long long y = q.front(); q.pop();
q.push(x + y);
ans += x*y;
}
cout<<ans;
}
방법 2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n; cin>>n;
vector<long long> v(n);
ll len = 0, ans = 0;
for(int i=0; i<n; i++) {
cin>>v[i];
len += v[i];
}
for(int i=0; i<n; i++) {
ans += v[i] * (len - v[i]);
len -= v[i];
}
cout<<ans;
}
'Algorithm' 카테고리의 다른 글
[BOJ] 로프 2217번 C++ (0) | 2024.09.13 |
---|---|
[BOJ] 사과나무 19539번 C++ (0) | 2024.09.11 |
[BOJ] 귀여운 라이언 15565번 C++ (1) | 2024.09.06 |
[BOJ] 가운데를 말해요 1655번 C++ (2) | 2024.09.04 |
[BOJ] 쇠막대기 10799번 C++ (0) | 2024.09.04 |