백준 No.9237 이장님 초대 - JAVA

 

문제

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

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

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

 

 

 

풀이

- 가장 오래걸리는 묘목을 먼저 심어야만 최대한 빠르게 이장님을 초대할 수 있는 방법이다.

- 내림차순을 정렬한다.

- for문을 만드는데 여기서 (i+1)+(arr[i]) 를 통해 해당 묘목이 언제 다 자라는 지 알 수 있다.

만약 주처음에 주어진 입력값을 내림차순으로 정렬한다면 4 3 3 2이다.

묘목을 구입한 날이 1일이기 때문 i는 1부터 시작해야한다.

(0+1)+(4)  => 묘목 구입 하루(시작이 그래서 1임) 5일 뒤에 나무생김

(1+1) + (3) => 두번쨰로 심으니 다음 날 심는다는 거임 다 성장하려면 5일

(2+1) + (3) => 세번째로 심으니 6일뒤에 완성

(3+1)+(2) => 6일뒤에 완성

- 이 값중에 가장 큰 값을 구한다 

- 문제에서 분명 다 자란 다음날 이장님을 초대한다고 되어있다.

그러면 가장 큰 값에 +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 Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Integer arr[] = new Integer[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr, Comparator.reverseOrder());

        for (int i = 0; i < N; i++) {
            arr[i] = (i+1)+(arr[i]);
        }

        Arrays.sort(arr,Comparator.reverseOrder());
        System.out.println(arr[0]+1);
    }
}