백준 14247 나무 자르기

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

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

    long long n, ans = 0;
    vector<pair<long long, long long>> tree;


    cin >> n;

    tree.resize(n);


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

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

    sort(tree.begin(), tree.end());

    for (int i = 0; i < n; i++) {
        ans += tree[i].second + tree[i].first * i;
    }

    cout << ans;


    return 0;
}

1. 문제

나무 n개의 초기 길이와 하루동안 자라는 길이가 주어진다. 매일 나무를 한 그루씩 잘라 얻으려고 할 때, 얻을 수 있는 최대 나무의 길이를 구하라.

2. 풀이

 그리디하게 풀 수 있는 문제이다. 나무는 자르지 않으면 계속 자라므로, 긴 나무를 오래 둘 수록 그 길이는 많이 증가한다. 즉, 짧은 나무를 일찍 자르고, 긴 나무를 늦게 자르면 최댓값을 구할 수 있다.

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

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

    sort(tree.begin(), tree.end());

pair로 초기 길이와 증가 길이를 입력받는다. 증가하는 길이를 기준으로 정렬할 것이므로 이를 first로 놓고, 정렬한다.

    for (int i = 0; i < n; i++) {
        ans += tree[i].second + tree[i].first * i;
    }

i+1일에 자른 나무의 길이는 나무의 초기 길이+하루에 증가하는 길이*i이므로 이를 적용하여 계산한다. 계산 결과를 출력하면 정답을 구할 수 있다.