[백준] 알고리즘 분류(그리디 알고리즘,JAVA)16435번, 스네이크버드

문제 링크

16435번: 스네이크버드

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 스네이크버드는 자신의 길이보다 작거나 같은 높이의 과일만 먹을 수 있습니다.

2. 과일을 1개 먹으면 길이가 1씩 늘어납니다.

3. 과일을 먹을 때 스네이크버드의 최대 길이를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 높이를 오름차순 정렬한 뒤, 낮은 곳의 과일부터 천천히 먹기 시작합니다.

 

3. 모든 과일을 먹은 후 스네이크버드의 길이를 결과로 출력합니다.

 

 

스네이크버드 과일 먹기

 

 

과일이 존재하는 높이를 오름차순 정렬한 뒤

 

 

높이가 낮은 과일부터 스네이크버드가 먹을 수 있는지 탐색합니다.

 

예제입력 1.

 

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

 

N = 3

L = 10

 

과일 높이 정보

	과일 1	과일 2	과일 3
높이	10	11	13

 

2. 높이를 오름차순 정렬한 뒤, 낮은 곳의 과일부터 천천히 먹기 시작합니다.

 

높이를 오름차순 정렬!

 

	과일 1	과일 2	과일 3
높이	10	11	13

 

낮은 곳부터 과일 먹기!

 

	과일 1	과일 2	과일 3
높이	10	11	13

 

스네이크버드 길이 : 10

과일 1 높이 : 10

과일 1 먹기 성공!

스네이크버드 길이 증가!

 

	과일 1	과일 2	과일 3
높이	10	11	13

 

스네이크버드 길이 : 11

과일 2 높이 : 11

과일 2 먹기 성공!

스네이크버드 길이 증가!

 

	과일 1	과일 2	과일 3
높이	10	11	13

스네이크버드 길이 : 12

과일 3 높이 : 13

과일 3 먹기 실패!

 

3. 모든 과일을 먹은 후 스네이크버드의 길이를 결과로 출력합니다.

 

모든 과일을 먹은 후 스네이크버드 길이 12를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 과일에 대한 정보를 띄어쓰기 기준 나누었습니다.
• Arrays.sort를 이용하여 과일의 높이 기준 오름차순 정렬하였습니다.
• 높이가 낮은 과일부터 탐색하여 스네이크버드의 길이를 증가시킵니다.
• 스네이크버드의 길이를 결과로 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));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine()," ");
        //과일의 높이 저장
        for(int i=0;i<N;i++)
            arr[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(arr);	//오름차순 정렬
        //낮은 과일부터 탐색 진행
        for(int i=0;i<N;i++){
            if(L >= arr[i])	//스네이크버드 길이보다 작거나 같으면 과일 섭취
                L++;	//길이 증가
        }
        bw.write(L + "");	//스네이크버드 길이 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}