[백준] 귀찮음 - c++

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 ≤ n ≤ 500,000) 이므로 최소비용의 값이 int 범위를 넘어갈 수 있다. 그래서 결과를 담는 변수를 long long으로 타입 지정해주어야 모든 서브태스크에서 정상적으로 동작한다.

처음엔 주어진 쇠막대기를 오름차순으로 정렬하여 일일히 누적합을 구해 tmp 배열에 저장하며 결과 값을 구했다.(코드 1)

하지만 친구 코드(코드 2)를 보니 배열을 sort하지 않고도 accumulate 누적합 내장 함수를 통해 코드를 간결하게 쓸 수 있는 문제였다.

반면에 지피티는 우선순위 큐를 써서 풀었다.

코드 1

#include<bits/stdc++.h>

using namespace std;

int n;
long long ans;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  vector<int> v(n);
  vector<int> tmp;
  for (int i = 0; i < n; i++)
    cin >> v[i];

  sort(v.begin(), v.end());
  for (int i = n - 1; i > 0; i--) {
    if (tmp.size()==0) {
      tmp.push_back(v[i]);
    }
    else {
      tmp.push_back(tmp[tmp.size() - 1] + v[i]);
    }
  }

  int j = tmp.size()-1;
  for (int i = 0; i < n-1; i++)
  {
    int now = v[i];
    ans += now * tmp[j];
    j--;
  }

  cout << ans << endl;

  return 0;
}

코드 2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


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

    int n;
    cin >> n;

    ll answer = 0;
    vector<ll> vec(n);

    for(int i=0; i<n; i++){
        cin >> vec[i];
    }

    ll length = accumulate(vec.begin(), vec.end(), 0);

    for(int i=0; i<n; i++){
        answer += (length-vec[i])*vec[i];
        length -= vec[i];
    }

    cout << answer;
    
}