[BOJ] 나무 자르기 14247번 C++

 

 

문제

영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n$n$일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다.

따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데,

나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오.

참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다.

입력

첫째 줄에는 나무의 개수 n개가 있다. 나무는 1번부터 n번까지 있다.

다음 줄에는 첫날 올라갔을 때 나무의 길이들 Hi가 n개가 순서대로 주어진다.

그 다음 줄에는 나무들이 자라는 길이 Ai가 n개가 순서대로 주어진다.

출력

영선이가 나무를 잘라서 구할 수 있는 최대 양을 출력하시오.

 

접근 방식

 문제 풀이에서 가장 중요한 것은 나무의 최대 양을 구하기 위해서는 나무의 성장 속도가 빠른 나무를 늦게 벨수록 더 많은 길이를 얻을 수 있다는 것이다.

따라서, 성장 속도가 느린 나무를 먼저 베어야 하기 때문에

성장 속도를 기준으로 정렬 후, 성장 속도가 작은 순서대로 나무를 베면 되는 간단한 문제이다!

 

 

코드

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

int main() {
    int n; cin>>n;
    vector<pair<int,int>> v(n);

    for(int i=0; i<n; i++) cin>>v[i].second;
    for(int i=0; i<n; i++) cin>>v[i].first;

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

    long long ans = 0;

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

    cout<<ans;
}