백준 9237번 - 이장님 초대 (C++)

유형: 그리디

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

9237번: 이장님 초대

 

풀이

첫 번째 나무는 1일차에 심는다. 그리고 0부터 시작한다.

[2, 3, 4, 3]의 경우, 2일 걸리는 나무를 첫 번째로 심는다 치면, 1일차에 0부터 시작, 3일차에 2가 된다.

그러니 각 나무가 다 자라는데 걸리는 시간은, 각 배열의 원소값 + (인덱스 + 1) 이다.

1일차부터 시작한다는 것은, 배열 순서를 세는 기준을 1로 잡는것과 동일하다.

제일 마지막 나무가 다 자라는 시간은, 위의 계산한 값 중 최댓값이다.

 

두 번째 예시 [39, 38, 9, 35, 39, 20]에 위 풀이를 적용해보자. 정답은 42일인데, 계산하면 44일로 나온다.

나무 배열의 순서를 지킬 필요가 없다는 뜻이다.

늦게 자라는 나무일수록 먼저 심는 것이 유리하다. 즉, 배열을 내림차순 정렬을 하면 된다.

[39, 39, 38, 35, 20, 9]로 정렬하면, 계산값의 최댓값은 41 이다.

문제에선 다 자란 날의 다음날에 초대한다고 써있기에, 41+1을 해서 정답 42가 나온다.

 

이 과정을 그대로 코드에 옮기면 끝!

코드를 완성하고 다시 보면, 문제에서 설명한 과정과 동일한 로직이 나온다.

#include "vector"
#include "algorithm"
#include "iostream"

using namespace std;

int solution(vector<int> arr){
    int cnt = -1, day = 1;

    // 내림차순으로 정리
    sort(arr.begin(), arr.end(), greater<>());

    for(auto now: arr){ // 원소값 + 심은 날짜
        cnt = max(cnt, day + now);
        day++;
    }

    cnt++; // 마지막 자란 다음날 초대하기에 ++
    return cnt;
}

int main(){
    ios::sync_with_stdio(0);

    vector<int> arr;
    int n; cin >> n;

    while (n--){
        int temp; cin >> temp;
        arr.push_back(temp);
    }

    cout << solution(arr) << endl;

    return 0;
}