https://www.acmicpc.net/problem/14247
영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다.
따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데,
나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오.
참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다.
첫째 줄에는 나무의 개수 n개가 있다.(1≤n≤100,000) 나무는 1번부터 n번까지 있다.
다음 줄에는 첫날 올라갔을 때 나무의 길이들 Hi가 n개가 순서대로 주어진다.(1≤Hi≤100,000)
그 다음 줄에는 나무들이 자라는 길이 Ai가 n개가 순서대로 주어진다.(1≤Ai≤10,000)
영선이가 나무를 잘라서 구할 수 있는 최대 양을 출력하시오.
5
1 3 2 4 6
2 7 3 4 1
64
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int N;
long long answer = 0;
cin >> N;
vector<long long> growValue(N);
for(int i = 0; i < N; i++){
int tmp;
cin >> tmp;
answer += tmp;
}
for(auto & i : growValue) cin >> i;
sort(growValue.begin(), growValue.end());
for(int i = 0; i < N; ++i){
answer += growValue[i] * i;
}
cout << answer << '\n';
return 0;
}
가장 길게자라는 놈을 마지막에 자른다고 생각하면 된다. 일단 모든 나무를 한번씩은 베어야 한다. 어차피 N개의 나무가 있을 것이고 N번 산에 왔다 갈테니까.
그럼 초기 상태의 나무들은 우선 모두 가져갈 수 있을 것이다. 나머지 나무들이 i 일째 일 때 나무 길이 증가량 만큼 answer에 저장하면 되는데 나무가 적게 크는 순서대로 저장해야 가장 많은 나무를 저장할 수 있다.