[백준] 알고리즘 분류(그리디 알고리즘,JAVA)9237번, 이장님 초대

문제 링크

9237번: 이장님 초대

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 묘목을 하나 심는데 1일이 걸립니다.

2. 묘목이 모두 나무가 된 후 다음날 이장님을 초대합니다.

3. 이장님을 초대하는 최소 값을 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 묘목의 성장일 기준 내림차순 정렬 후, 묘목의 가장 성장일 큰 것부터 심기 시작합니다.

 

3. 모든 묘목이 나무가 되었을 때 날짜를 결과로 출력합니다.

 

 

묘목 심기 및 성장

 

※묘목을 성장일 큰 것부터 심는 이유는 나무가 되는데 오래걸리기 때문에 먼저 성장시키게 하기 위해서입니다.

 

 

 

묘목의 성장일이 큰 것부터 심기시작합니다.

 

묘목을 심은 날짜 + 성장일 = 나무가 되는 날

 

 

모든 묘목을 심었을 때 "나무가 되는 날"이 가장 큰 값이 모든 묘목이 나무가 되었을 때 날짜입니다.

 

모든 묘목이 나무가 되었을 때 날짜 + 1 = 이장님이 오는 날

 

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N = 6

 

묘목 성장일

묘목 1	묘목 2	묘목 3	묘목 4	묘목 5	묘목 6
39	38	9	35	39	20

 

2. 묘목의 성장일 기준 내림차순 정렬 후, 묘목의 가장 성장일 큰 것부터 심기 시작합니다.

 

묘목 성장일 기준 내림차순 정렬!

 

묘목 1	묘목 5	묘목 2	묘목 4	묘목 6	묘목 3
39	39	38	35	20	9

 

묘목 가장 성장일 큰 것부터 심기 시작!

1일차

묘목 1 심기!

나무 성장일 : 39 + 1 = 40

 

2일차

묘목 5 심기!

나무 성장일 : 39 + 2 = 41

 

3일차

묘목 2 심기!

나무 성장일 : 38 + 3 = 41

 

4일차

묘목 4 심기!

나무 성장일 : 35 + 4 = 39

 

5일차

묘목 6 심기!

나무 성장일 : 20 + 5 = 25

 

6일차

묘목 3 심기!

나무 성장일 : 9 + 6 = 15

 

 

3. 모든 묘목이 나무가 되었을 때 날짜를 결과로 출력합니다.

 

모든 묘목이 나무가 되었을 때 날짜 : 41

 

이장님은 다음날 오시기 때문에 : 41 + 1 = 42

 

42을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenzier를 이용하여 묘목의 성장일을 띄어쓰기 기준 나누었습니다.
• Arrays.sort를 이용해서 묘목의 성장일 기준 내림차순 정렬하였습니다.
• 1일부터 성장일 큰 것부터 심을 때 나무가 되는 날짜의 최대값을 구합니다.
• 나무가 되는 날짜의 최대값 + 1(이장님 오는 날)결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Integer[] num = new Integer[N];
        //묘목 성장일 입력값 저장
        for(int i=0;i<N;i++)
            num[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(num, Collections.reverseOrder());	//내림차순 정렬
        int max = Integer.MIN_VALUE;
        //1일부터 성장일 큰 것부터 심기 및 나무가 되는 요일 최대값 구하기
        for(int i=0;i<N;i++)
            max = Math.max(max, num[i] + i + 1);
        
        bw.write((max+1) + "");	// 이장님이 오시는 날 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();	
        br.close();
    }
}