[백준 C++] 9237번 : 이장님 초대

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

9237번: 이장님 초대

풀이 :

- 묘목이 자라는데 걸리는 시간이 주어지고, 각 묘목은 심는데 하루가 걸린다.

   나무가 다 자란 후 이장님을 초대해야 하니 최댓값을 구할 수 있도록 순서를 정해야 한다

- 가장 오래 걸리는 나무부터 차례로 심어야 하니 먼저 내림차순으로 정렬을 해준다

- 각 묘목이 다 자라기까지 걸리는 시간은 묘목이 원래 자라는데 걸리는 시간 + 이전 묘목들과 현재 묘목을 심는데 걸리는 시간이다

- 배열을 탐색하며 최댓값을 구하고, 나무가 다 자란 후에 초대해야 하기 때문에 최댓값에 1을 더한다

예제 1을 보자

4
2 3 4 3

4 3 3 2 //내림차순으로 정렬
4 = 4+1 -> 5일 걸린다
3 = 3+2 -> 5일 걸린다 4를 심는데 걸리는 시간 1, 3을 심는데 걸리는 시간 1, 총 2를 더한다
3 = 3+3 -> 6일 걸린다
2 = 2+4 -> 6일 걸린다
최댓값 6+1 -> 7일에 이장님을 초대할 수 있다

코드 :

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

int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n, MAX = 0, num, arr[100005];

    cin >> n;
    for(int i=1; i<=n; i++){ //나중에 계산하기 편하게 1부터 시작
        cin >> arr[i];
    }
    sort(arr+1,arr+n+1, greater<>()); //내림차순으로 정렬
    for(int i=1; i<=n; i++){
        num = arr[i]+i; //묘목이 자라는데 걸리는 시간+i(심는 시간)
        MAX = max(MAX,num); //최댓값 갱신
    }
    cout << MAX+1 << '\n';
}