백준 16435 - 스네이크버드(자바 - 그리디)

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

16435번: 스네이크버드

 

* 문제 요약

스네이크버드는 뱀과 새의 모습을 닮은 귀여운 생물체입니다.

스네이크버드의 주요 먹이는 과일이며, 과일 하나를 먹으면 길이가 1 만큼 늘어납니다.

과일들은 지상으로부터 일정 높이를 두고 떨어져 있으며 i (1 <= i <= N) 번째 과일의 높이는 hi 입니다.

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

스네이크버드의 처음 길이가 L 일 때 과일들을 먹어 늘릴 수 있는 최대 길이를 구하세요

 

* 입력

첫번째 줄에 과일의 갯수 N (1 <= N <= 1,000) 과 스네이크버드의 초기 길이 정수 L (1 <= L <= 10,000) 이 주어집니다.

두번째 줄에는 정수 h1, h2, ... hN (1 <= hi <= 10,000) 이 주어집니다.

 

* 출력

첫번째 줄에 스네이크버드의 최대 길이를 출력합니다.

 

* 예시

 

* 해결 과정

과일들의 위치를 바꾸지 말라는 규칙은 없으므로 과일들을 오름차순 정렬해준 다음, 과일 배열을 처음부터 탐색하면서 매 반복마다 과일의 위치가 현재 스네이크버드의 크기보다 작거나 같을 경우 스네이크버드의 크기를 1 늘려주고,

그렇지 않을 경우 반복문을 종료해준다.

그렇게 하여 최종적으로 성장한 스네이크버드의 크기를 출력해주면 끝

 

* 코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");

        int count = Integer.parseInt(input[0]);
        int size = Integer.parseInt(input[1]);
        int[] fruits = new int[count];
        input = br.readLine().split(" ");
        for (int i = 0; i < fruits.length; i++) {
            fruits[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(fruits);

        for (int i = 0; i < fruits.length; i++) {
            if (fruits[i] <= size) {
                size++;
            } else
                break;
        }

        bw.write(size + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

스네이크버드의 크기가 최대가 되려면 최대한 많은 숫자의 과일을 먹을 수 있어야 한다.

그러므로 과일의 위치를 오름차순으로 정렬시켜서 가장 위치가 낮은 과일부터 먹게 했다.

최대 크기를 만들기 위해 정렬을 통해서 최적의 경우를 찾았으므로 정렬 및 그리디 알고리즘 문제에 해당된다.