[그리디] 코딩테스트 문제 TIL (스네이크버드) - 백준 16435번

1. 오늘의 학습 키워드

• 그리디
• 정렬

---

2. 문제: 16453. 스네이크버드

• 단계: 🥈 실버 5단계
• 주제:
  • 그리디 알고리즘
  • 정렬
• 출처: https://www.acmicpc.net/problem/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

3 10
10 11 13

예제 출력 1

12

스네이크버드의 처음 길이는 10이며 1번 과일을 먹은 후 길이가 11이 됩니다. 이후 2번 과일을 먹으면 길이가 12가 됩니다. 더 이상 먹을 수 있는 과일이 없으므로 최대 길이는 12가 됩니다.

예제 입력 2

9 1
9 5 8 1 3 2 7 6 4

예제 출력 2

10

---

3. 문제 풀이

Step1. 문제 이해하기

스네이크버드는 자신보다 높이가 낮거나 같은 과일을 먹으면 길이가 1만큼 증가합니다. 과일의 높이가 랜덤하게 주어지므로, 이를 정렬한 후 스네이크버드가 먹을 수 있는 과일을 순서대로 먹도록 해야 최대의 길이를 얻을 수 있습니다.

입출력은 다음과 같습니다.

• Input:
  • 첫 번째 줄에 과일의 개수 N과 스네이크버드의 초기 길이 정수 L이 주어집니다.
    • N은 1이상 1000이하, L은 1이상 10000이하로 주어집니다.
  • 두 번째 줄에는 과일의 높이 배열이 주어집니다.
• output:
  • 스네이크버드의 최대 길이를 출력합니다.

Step2. 문제 분석하기

1. 과일의 높이를 오름차순으로 정렬합니다.
2. 정렬된 높이를 순회하며:
   • 스네이크버드의 현재 길이가 과일의 높이보다 크거나 같으면 과일을 먹고 길이를 1 증가시킵니다.
   • 그렇지 않으면 종료합니다.
3. 순회를 마친 후 스네이크버드의 길이를 출력합니다.

그리디 알고리즘을 사용하여 매 순간 가능한 선택(과일을 먹기)을 최대로 하여 최종 결과를 도출합니다.

Step3. 코드 설계

Step4. 코드 구현

import sys
N, L = map(int, sys.stdin.readline().split())
heights = list(map(int, sys.stdin.readline().split()))
def sol(L, heights):
    heights.sort()
    for height in heights:
        if L >= height:
            L += 1
        else:
            break
    print(L)
sol(L=L, heights=heights)

• 코드 설명:
  1. 정렬:
     • heights.sort()를 통해 과일의 높이를 오름차순으로 정렬합니다. 이렇게 하면 스네이크버드가 가장 낮은 과일부터 순서대로 먹을 수 있습니다.
  2. 반복:
     • 정렬된 높이를 순회하며 스네이크버드의 길이 L로 먹을 수 있는 과일을 먹습니다.
     • 먹으면 길이를 1만큼 증가시킵니다.
     • 먹을 수 없는 과일이 나오면 반복을 종료합니다.
  3. 출력:
     • 최종적으로 증가한 길이를 출력합니다.
• 시간 복잡도: $O(N \log N)$
• 결과:
  

---

4. 마무리

이번 문제는 그리디 알고리즘을 활용하여 매 순간 최적의 선택(가장 낮은 높이의 과일부터 먹기)을 반복하여 최종 결과를 얻는 문제였습니다. 과일의 높이를 정렬한 후 스네이크버드가 먹을 수 있는 과일을 순차적으로 처리해 최적의 해를 도출할 수 있었습니다. 시간 복잡도 $O(N \log N)$으로 효율적으로 해결 가능한 문제였으며, 간단한 로직으로 구현할 수 있어 깔끔한 풀이가 가능했습니다.