백준 9237 이장님 초대 JAVA 풀이 (그리디, 정렬, 시간복잡도)

🔗 문제 링크

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

---

📌 문제 개요

나무를 하루에 하나씩 심을 수 있고,
각 나무는 자라는 데 시간이 다르게 걸린다.

 

모든 나무가 다 자란 다음 날 이장님을 초대해야 할 때,
가장 빠른 초대 날짜를 구하는 문제

---

📌 접근 방법

이 문제의 핵심은 심는 순서

• 오래 걸리는 나무를 뒤에 심으면 전체 시간이 늦어짐
• 따라서 오래 걸리는 나무부터 먼저 심는 것이 최적

 즉, 내림차순 정렬 후 순서대로 심기

---

📌 핵심 아이디어

• i번째 나무는 (i + 1)일에 심는다
• 해당 나무 완료일:

tree[i] + (i + 1)

 

• 전체 완료일은 최댓값
• 초대는 다음 날이므로 +1

---

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] tree = new int[N];

        String[] input = br.readLine().split(" ");
        for(int i = 0; i < N; i++){
            tree[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(tree);

        int max = 0;

        for(int i = 0; i < N; i++){
            int day = tree[N - 1 - i] + (i + 1);
            max = Math.max(max, day);
        }

        System.out.println(max + 1);
    }
}

---

🧾 정리

• 그리디 문제 (정렬 기반)
• 오래 걸리는 작업 먼저 처리 → 최적 전략
• 핵심 공식: