[백준 16208] 귀찮음 (C#, C++) - soo:bak

문제 링크

16208번 - 귀찮음

설명

막대를 N개의 조각으로 자를 때, 각 조각의 길이가 주어집니다. 막대를 두 조각으로 자를 때 비용은 두 조각 길이의 곱입니다. 막대를 모두 자르는 데 필요한 최소 비용을 구하는 문제입니다.

접근법

자르는 순서와 관계없이 총 비용은 모든 조각 쌍의 길이 곱의 합과 같습니다. 따라서 최소 비용을 구하려면 모든 쌍의 곱을 더하면 됩니다.

먼저 모든 조각 길이의 합을 구합니다. 각 조각을 순회하며 현재 조각 길이와 남은 조각들의 합을 곱하여 누적합니다. 이렇게 하면 모든 쌍의 곱을 한 번의 순회로 계산할 수 있습니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var arr = Array.ConvertAll(Console.ReadLine()!.Split(), long.Parse);

    var total = 0L;
    foreach (var v in arr) total += v;

    var ans = 0L;
    foreach (var v in arr) {
      total -= v;
      ans += v * total;
    }

    Console.WriteLine(ans);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;

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

  int n; cin >> n;
  vl a(n);
  ll total = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    total += a[i];
  }

  ll ans = 0;
  for (int i = 0; i < n; i++) {
    total -= a[i];
    ans += a[i] * total;
  }

  cout << ans << "\n";

  return 0;
}