[백준 16435] 스네이크버드 (C#, C++) - soo:bak

문제 링크

16435번 - 스네이크버드

설명

N개의 과일이 있고 각 과일의 높이가 주어지는 상황에서, N (1 ≤ N ≤ 1,000), 초기 길이 L (1 ≤ L ≤ 10,000), 그리고 각 과일의 높이 (1 ≤ 높이 ≤ 10,000)가 주어질 때, 스네이크버드가 도달할 수 있는 최대 길이를 구하는 문제입니다.

스네이크버드는 자신의 길이보다 작거나 같은 높이의 과일만 먹을 수 있으며, 과일을 하나 먹을 때마다 길이가 1씩 증가합니다.

접근법

가장 낮은 과일부터 순서대로 먹는 그리디 전략을 사용합니다.

높은 과일을 먼저 먹으면 길이가 늘어나지 않아 더 낮은 과일을 먹을 기회를 잃지만, 낮은 과일부터 먹으면 길이가 증가하여 원래 먹을 수 없던 높은 과일도 먹을 수 있게 됩니다.

모든 과일을 높이 순으로 정렬합니다. 정렬된 순서대로 과일을 확인하면서, 현재 길이 이하인 과일은 먹고 길이를 1 증가시킵니다.

어떤 과일을 먹을 수 없다면 그 뒤의 과일들은 모두 더 높으므로 더 이상 먹을 수 없습니다.

예를 들어, 초기 길이가 10이고 과일 높이가 [9, 5, 10, 15, 7]인 경우:

정렬하면 [5, 7, 9, 10, 15]가 됩니다. 높이 5는 10 이하이므로 먹으면 길이가 11이 됩니다. 높이 7은 11 이하이므로 먹으면 길이가 12가 됩니다. 같은 방식으로 9와 10도 먹을 수 있어 길이는 14가 됩니다.

하지만 높이 15는 14보다 크므로 먹을 수 없습니다. 따라서 최종 길이는 14입니다.

시간 복잡도는 O(N log N)입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var first = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var n = first[0];
      var len = first[1];
      
      var fruits = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      Array.Sort(fruits);
      
      foreach (var h in fruits) {
        if (h <= len) len++;
        else break;
      }
      
      Console.WriteLine(len);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, len;
  cin >> n >> len;
  
  vi fruits(n);
  for (int i = 0; i < n; i++)
    cin >> fruits[i];
  
  sort(fruits.begin(), fruits.end());
  
  for (int h : fruits) {
    if (h <= len) len++;
    else break;
  }
  
  cout << len << "\n";
  
  return 0;
}