BOJ_16208 : 귀찮음 (C++)

풀이 방법

 

원하는 쇠막대의 수와 원하는 쇠막대의 길이가 주어진다.

처음에 문제 이해가 안되서 접근이 많이 어려웠는데, 이해하고 보면 단순한 수학 및 구현 문제이다.

 

주어진 예제를 들어 이해해보면,

 

4

3 5 4 2

 

로 주어지는데,

 

주어진 총 쇠막대 길이의 합을 구하면 3 + 5 + 4 + 2 = 14 이다.

 

14 -> 3(원하는 쇠막대 길이 첫번째 값), 11( = 14 - 3 = 총 쇠막대 길이 - 쇠막대 첫번째 길이 값) : 3 * 11 = 33
11 - > 5(원하는 쇠막대 길이 두번째 값), 6( = 11 - 5 = 현재 남은 쇠막대 길이 - 쇠막대 두번째 길이 값) : 5 * 6 = 30
6 -> 4(원하는 쇠막대 길이 세번째 값), 2( = 6 - 4 = 현재 남은 쇠막대 길이 - 쇠막대 세번째 길이 값) : 4 * 2 = 8
2 -> 2(원하는 쇠막대 길이 네번째 값), 0( = 2 - 2 = 현재 남은 쇠막대 길이 - 쇠막대 네번째 길이 값) : 2 * 0 = 0

 

답은, 33 + 30 + 8 + 0 = 71 이다.

 

즉, 주어진 각 쇠막대 길이를 합한 쇠막대 길이의 총 합을 구한 후, 쇠막대 길이를 하나씩 빼줄때 나오는 그 두 개의 값을 곱하여 더한 합이 구해야 하는 값이였다.

 

 

 

코드

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
#include <limits.h>
#include <regex>
#include <sstream>
#include <tuple>    
using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 막대 잘라서 n개의 쇠막대 만들기

    // x + y 막대 길이를 x, y 두개로 자를 때, x*y 비용 필요
    // 최소 비용으로 n개의 쇠막대 얻기a

    int n; // 원하는 쇠막대 수
    cin >> n;

    vector <long long> v; // 원하는 쇠막대 길이

    long long sum = 0;

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

    long long ans = 0;
    int idx = 0;

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

    cout << ans << "\n";

    return 0;
}