#9237 : 이장님 초대

풀이방법

사용된 것:

그리디 알고리즘

정렬

 

2022.02.24

자라는 데 가장 오래 걸리는 나무부터 심어야 한다.

그러므로 자라는 데 걸리는 일 수를 내림차순 정렬해준다.

정렬된 배열의 앞에 있는 나무부터 심는다.

 

한 나무가 다 자라는 날의 날짜는,

(이 나무를 심기 전에 다른 나무를 심느라 보낸 시간) + (이 나무를 심는 데 걸리는 하루) + (이 나무가 자라는 데 걸리는 시간) 이다.

 

모든 나무에 대하여, 다 자라는 날의 날짜를 구한다.

다 자라는 날이 가장 나중인 놈이 있을 것이다.

그놈이 다 자라는 날짜가 바로 정답이다.

 

코드

Java(2022.02.24)

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

public class Main {

	static int n;	//나무의 개수
	static Integer[] days;	//나무별 자라는 데 걸리는 시간
	static int end;	//나무가 모두 자라는 데 걸리는 시간
	static StringTokenizer st;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//나무의 개수 읽어오기
		n = Integer.parseInt(br.readLine());
		days = new Integer[n];
		//나무별 자라는 데 걸리는 시간 읽어오기
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++) {
			days[i] = Integer.parseInt(st.nextToken());
		}
		//걸리는 시간을 내림차순 정렬하기
		Arrays.sort(days, Collections.reverseOrder());
		//정답 구하기
		end = 0;
		for(int i = 0; i<n; i++) {
			//cur = 이번 나무가 다 자라는 날짜(이번 나무를 심은 날 + 심는데 걸린 하루 + 자라는 데 걸리는 시간)
			int cur = (i + 1) + 1 + days[i];
			//cur 값들 중 최댓값이 정답임
			if(end<cur) end = cur;
		}
		//정답 출력
		System.out.print(end);

	}

}