[백준/BOJ] 14247번 나무 자르기 (C++)

www.acmicpc.net/problem/14247

14247번: 나무 자르기

그리디 유형 문제입니다.

나무가 자라는 가중치 값을 기준으로 오름차순 정렬을 한 후, 가중치가 작은 값부터 나무를 자르면 해결할 수 있는 문제입니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int cmp(pair<long long, long long> a, pair<long long, long long> b) {
    return a.second < b.second; // 가중치 값을 기준으로 오름차순
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;
    
    vector<long long> height(n);
    vector<long long> weight(n);
    vector<pair<long long, long long > > tree;
    
    for(int i = 0; i < n; i++) {
        cin>>height[i];
    }
    
    for(int i = 0; i < n; i++) {
        cin>>weight[i];
    }
    
     for(int i = 0; i < n; i++) {
        tree.push_back({height[i], weight[i]});
    }
    
    sort(tree.begin(), tree.end(), cmp);
    
    long long answer = 0;
    for(int i = 0; i < n; i++) {
        answer += tree[i].first + tree[i].second * i;
    }
    cout<<answer;
}