문제
스네이크버드는 뱀과 새의 모습을 닮은 귀여운 생물체입니다.
스네이크버드의 주요 먹이는 과일이며 과일 하나를 먹으면 길이가 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 늘어난다. 따라서 낮은 과일부터 차례로 먹어야 가능한 과일을 최대한 많이 연결할 수 있다.
코드는 과일 높이를 오름차순으로 정렬한 뒤 앞에서부터 확인한다. 현재 길이 L로 먹을 수 있는 과일이면 L을 1 늘리고, 처음으로 먹을 수 없는 과일을 만나면 그 뒤 과일은 더 높거나 같으므로 더 볼 필요가 없다.
핵심은 가장 낮은 과일을 먼저 먹는 선택이 항상 손해가 없다는 점이다. 먹을 수 있는 과일을 뒤로 미뤄도 길이가 늘지 않으므로, 가능한 순간 바로 먹는 것이 최선이다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int[] height;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int L = Integer.parseInt(st.nextToken());
height = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < N; i++)
height[i] = Integer.parseInt(st.nextToken());
Arrays.sort(height);
int ans = solve(N, L);
System.out.println(ans);
}
static int solve(int N, int L) {
for (int i = 0; i < N; i++) {
if (height[i] > L)
break;
L++;
}
return L;
}
}복잡도
- 시간 복잡도: 과일 높이를 정렬하므로 이다.
- 공간 복잡도: 과일 높이 배열을 저장하므로 이다.
마무리
먹을 수 있는 과일부터 순서대로 처리하면 스네이크버드 길이는 자연스럽게 늘어난다.
