16435번: 스네이크버드
첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다.
www.acmicpc.net
문제
스네이크버드는 뱀과 새의 모습을 닮은 귀여운 생물체입니다.
스네이크버드의 주요 먹이는 과일이며 과일 하나를 먹으면 길이가 1만큼 늘어납니다.
과일들은 지상으로부터 일정 높이를 두고 떨어져 있으며 $i (1 ≤ i ≤ N)$ 번째 과일의 높이는 $h_i$입니다.
스네이크버드는 자신의 길이보다 작거나 같은 높이에 있는 과일들을 먹을 수 있습니다.
스네이크버드의 처음 길이가 $L$일때 과일들을 먹어 늘릴 수 있는 최대 길이를 구하세요.
입력
첫 번째 줄에 과일의 개수 $N$ $(1 ≤ N ≤ 1,000)$ 과 스네이크버드의 초기 길이 정수 $L$ $(1 ≤ L ≤ 10,000)$ 이 주어집니다.
두 번째 줄에는 정수 $h_1, h_2, ..., h_N$ $(1 ≤ h_i ≤ 10,000)$ 이 주어집니다.
출력
첫 번째 줄에 스네이크버드의 최대 길이를 출력합니다.
코드
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
less, equal, greater = [], [], []
for a in arr:
if a < pivot:
less.append(a)
elif a == pivot:
equal.append(a)
else:
greater.append(a)
return quick_sort(less)+equal+quick_sort(greater)
n, l = map(int, input().split())
h = list(map(int, input().split()))
h = quick_sort(h)
for i in range(n):
if l < h[i]:
break
l += 1
print(l)
주어진 과일들의 높이를 오름차순으로 정렬하여 낮게 위치한 과일부터 스네이크버드가 먹을 수 없을 때까지 먹으면 된다.
사실 내장함수 sort()를 사용하면 더 짧고 빠르게 풀이할 수 있지만, 퀵정렬을 구현해보고 싶어서 따로 구현하여 사용하였다.
'문제풀이 > Greedy' 카테고리의 다른 글
[Python/파이썬] 백준 4796번 캠핑 (0) | 2024.02.28 |
---|---|
[Python/파이썬] 백준 2847번 게임을 만든 동준이 (0) | 2024.01.25 |
[Python/파이썬] 백준 16206번 롤케이크 (0) | 2023.12.30 |
[Python/파이썬] 백준 1744번 수 묶기 (1) | 2023.12.23 |
[Python/파이썬] 백준 6137번 문자열 생성 (2) | 2023.11.27 |