(C++) - 백준(BOJ) 16208 : 귀찮음

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

16208번: 귀찮음

간단한 greedy 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

수의 개수 n, 필요한 막대의 길이를 저장할 length, 정답을 출력할 ans, 필요 막대들의 정보를 입력받을 vector v를 선언 후 입력받습니다.

📔 풀이과정

n개의 막대들의 총 길이를 length에 저장합니다. 어떤 방법을 사용해도 결국에는 length길이의 막대를 n-1번 잘라야 합니다. 결국에는 x*y가 n-1번 비용으로 지불하게 됩니다. 따라서 n만큼 for loop를 수행해 ans에 (v[i] * length - v[i])만큼 더해주고 length -= v[i]해주는 공식이 성립합니다. 

📔 정답출력

ans를 출력해줍니다.

---

📕 Code

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

ll n, length, ans;
vector <ll> v;

int main(){
  cin >> n;
  v.resize(n);
  for(int i = 0; i < n; i++) cin >> v[i], length += v[i];
  for(int i = 0; i < n; i++){
    ans += v[i] * (length - v[i]);
    length -= v[i];
  }
  cout << ans;
}