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

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

9237번: 이장님 초대

 

문제

농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다.

상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다.

상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최대한 빨리 초대하려고 한다. 이장님을 며칠에 초대할 수 있을까?

입력

입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000)

출력

첫째 줄에 며칠에 이장님을 초대할 수 있는지 출력한다. 답이 여러 가지인 경우에는 가장 작은 값을 출력한다. 묘목을 구입한 날이 1일이다.

 

풀이1 - 외않되?

직접 시뮬레이션을 돌리는 방식이다

하루가 지나감에따라 나무가 자라는 방식.. 인데.. 

예제 다 맞는데...

맞 왜 틀?

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

using namespace std;

bool compare (int i, int j){
    return i > j;
}

int main() {
    
    int n;
    vector <int> tree;

    cin >> n;
    
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        tree.push_back(tmp);
    }
    
    sort(tree.begin(), tree.end(), compare);
    
    int day = 1;
    for(int i=0, growing = tree[0]; true; i++){

        growing--;
        
        if(growing <= 0)
            break;
        
        if(i<n)
            growing = max(tree[i], growing);
        
        day++;
    }
    
    cout << day+1;
    
    return 0;
}

 

풀이2 - 성공

그냥 계산했다

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

using namespace std;

bool compare (int i, int j){
    return i > j;
}

int main() {
    
    int n;
    vector <int> tree;

    cin >> n;
    
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        tree.push_back(tmp);
    }
    
    sort(tree.begin(), tree.end(), compare);
    
    int day = tree[0] + 1;
    for(int i=0; i<n; i++){
        day = max(day, tree[i]+i+1);
    }
    
    cout << day + 1;
    
    return 0;
}