[알고리즘]_그리디 알고리즘_이장님 초대👴🏼 (백준 No.9237)

문제

농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다.
상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다.
상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최대한 빨리 초대하려고 한다. 이장님을 며칠에 초대할 수 있을까?

---

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

---

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

---

💡 코드

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

public class No_9237 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Integer[] t = new Integer[n];
		//공백 단위로 입력
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			t[i] = Integer.parseInt(st.nextToken());
		}
		//내림차순
		Arrays.sort(t, Comparator.reverseOrder());
		int day=0;
		int max=0;
		for (int i = 0; i < n; i++) {
			day++;//1일에 1개씩만 심을 수 있으니깐
			if(max<=t[i]+day){
				max=t[i]+day;
			}
		}
		System.out.println(max+1);
	}
}

👩🏻‍💻 풀이

• 입력받은 묘목들을 내림차순으로 정렬한다. (가장 오래 걸리는 순서대로)
• 하루에 묘목은 하나만 심을 수 있으니 day로 날짜를 조절한다.
• day와 입력받은 묘목의 자라는 날짜를 더해 max보다 크다면 최대 요일을 변경한다.
• 문제조건에 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다.가 있으므로 max에 +1을 해 정답을 출력한다