백준 16435번: 스네이크 버드 (Python/Java)

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

16435번: 스네이크버드

접근

---

그리디 알고리즘의 개념을 익히는 단계에서 풀어볼 만한 아주 간단한 문제였다.

그리디 알고리즘은 현재 단계에서 최선의 선택을 해야 한다. 이 문제에서 최선의 선택이란, 자신이 먹을 수 있는 가장 낮은 높이의 과일부터 순서대로 하나씩 먹으며 길이를 늘리는 것이다. 이를 위해 과일 리스트들을 높이가 낮은 순서대로 정렬한 뒤, 현재 스네이크버드의 길이와 과일의 높이를 비교해 먹거나 안 먹거나를 선택하면 된다.

높이가 낮은 순서대로 정렬해뒀기 때문에 자신이 못 먹는 과일이 나오는 순간 그 뒤는 더 이상 비교해볼 필요가 없다. 자신이 못 먹는 과일이 나오는 순간 바로 스네이크 버드의 길이를 출력해준다.

풀이

---

Python

fruitNum, snakebird = map(int, (input()).split())

fruitList = []
fruits = (input()).split()
for i in range(fruitNum):
    fruitList.append(int(fruits[i]))
fruitList = sorted(fruitList)

for i in range(fruitNum):
    if snakebird >= fruitList[i]:
        snakebird += 1
    else:
        break

print(snakebird)

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);
        
        String[] firstLine = (scan.nextLine()).split(" ");
        int fruitNum = Integer.parseInt(firstLine[0]), snakebird = Integer.parseInt(firstLine[1]);

        int[] fruitList = new int[fruitNum];
        String[] secondLine = (scan.nextLine()).split(" ");
        for(int i = 0 ; i < fruitNum ; i++){
            fruitList[i] = Integer.parseInt(secondLine[i]);
        }
        Arrays.sort(fruitList);

        for(int i = 0 ; i < fruitNum ; i++){
            if(snakebird >= fruitList[i]){
                snakebird++;
            }else {
                break;
            }
        }

        System.out.println(snakebird);

    }

}

후기

---

여태까지는 구현, 그래프 문제를 중심으로 알고리즘 풀이를 했기 때문에 그리디 알고리즘 공부에 대한 필요성을 느끼고 알고리즘 개념을 익혔다.
초반부터 바로 난이도 높은 문제를 풀면 힘들 것 같아 쉬운 문제를 골랐더니... 생각보다 너무 쉬운 문제를 골라버렸다;;;
어쨌든 그리디 알고리즘의 기초적인 적용에 대해 생각해볼 수 있는 연습 문제라고 생각하면 나쁘지 않았던 문제라고 생각한다.