백준[16435] - 스네이크버드

• 문제: https://www.acmicpc.net/problem/16435
• 분류: 정렬, 그리디
• 난이도: S5
• 소요시간: 5m
• 자아성찰:
  • 이전에 알고리즘을 풀었을 때에도 그리디에 많이 약했었다.
  • 가장 기초적인 그리디에 대해 다시 이해하고자 쉬운 문제로 골랐다.
  • 내 기준 그리디의 핵심은 '문제를 스스로 꼬아 풀지 말자' 인데, 이 문제가 그 핵심을 잘 적용할 수 있었던 문제인 것 같다.
  • N <= 1000, L, h <= 10000이다. 숫자가 크지 않다. 단순하게 생각했다.
  • 무슨 과일을 먹든 길이는 1 증가한다.  => 가장 만만한(가장 높이가 낮은) 과일부터 먹으면서 길이를 늘리는 것이 무조건적으로 최대 효율을 낼 수 있다.
  • 과일을 먹는 순서는 상관 없다. => 단순하게 정렬로 가장 높이가 낮은 과일부터 차례대로 먹어가며 길이를 늘린다.
  • 문제가 아무리 어려워보여도 일단 단순하게 생각하는 습관을 길러보자. (브루트포스, 그리디)
  • 단순함을 잘 사용하면 생각보다 쉽게 풀린다!

16435번: 스네이크버드

---

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

public class B_16435 {

    static int N, L;
    static int[] h;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        h = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            h[i] = Integer.parseInt(st.nextToken());
        }
        // 높이 낮은 순으로 과일 정렬
        Arrays.sort(h);
        // 가장 낮은 높이의 과일부터 차례로 먹어가며 길이를 늘리자.
        for (int i = 0; i < N; i++) {
            if (L >= h[i]) {
                L++;
            }
        }
        System.out.println(L);
    }
}