백준 9237번 <이장님 초대>

백준 알고리즘 9237번

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

9237번: 이장님 초대

---

9237번

나무 묘목 N개를 모두 심고 이장님을 최대한 빨리 초대할 때 며칠이 걸리는지 구하여라.

묘목을 구입한 날이 1일이고 묘목 하나를 심는데 걸리는 시간이 1일이다.

 

입력으로 첫 줄에 묘목의 수 N이 주어지고 그 다음 줄에 각 묘목이 자라는데 걸리는 시간이 주어진다.

 

출력으로는 이장님을 며칠 뒤에 초대할 수 있는지 출력한다.

---

문제 해결

그리디 알고리즘으로 해결할 수 있다.

 

먼저 이장님을 최대한 빨리 초대해야하기 때문에 다 자라는데 가장 오래 걸리는 묘목을 먼저 심는다.

그래야 빨리 자라는 묘목과 비슷한 시간이 걸린다고 할 수 있다.

---

코드

package bj9237;

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());
		String[] inArr = br.readLine().split(" ");
		int[] tree = new int[N];
		for (int i = 0; i < N; i++) {
			tree[i] = Integer.parseInt(inArr[i]) * (-1);
		}

		Arrays.sort(tree);
		int answer = 0;
		int time = 2;
		for (int i = 0; i < N; i++) {
			answer = Math.max(answer, time + (tree[i] * (-1)));
			time++;
		}

		System.out.println(answer);

	}

}

---

결과

---