
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
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
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()); // 스네이크버드 초기 길이
// 과일 높이 정보받기
int[] A = new int[N];
st = new StringTokenizer(br.readLine());
for (int i=0; i<N; i++){
A[i] = Integer.parseInt(st.nextToken());
}
// 과일높이 오름차순 정렬
Arrays.sort(A);
for (int i=0; i<N; i++){
if (L >= A[i]){
L++; // 먹을 수 있는 과일이라면 먹고 길이 1늘어난다.
}else{
break; // 먹을 수 없다면 멈춘다.
}
}
System.out.println(L);
}
}
- 그리디를 활용한문제
- 과일 개수N, 스네이크버드 초기길이 L을 입력받는다.
- 과일 높이정보를 받아서 A배열에 저장한다.
- 배열 A를 오름차순으로 정렬한다.
- i=0 ~ N-1까지 순회하면서, L>=A[i] 라면 L을 1증가시켜준다.
- 만약 L < A[i] 이라면 break하고 함수를 종료한다.
- 마지막에 L크기를 출력해주면 된다.
'코딩테스트 > 백준' 카테고리의 다른 글
[백준 2579] 계단 오르기 (Java) - 다이나믹 프로그래밍 (1) | 2025.04.22 |
---|---|
[백준 1003] 피보나치 함수 (Java) - 다이나믹 프로그래밍 (0) | 2025.04.21 |
[백준 2667] 단지번호붙이기 (Java) - BFS (0) | 2025.04.19 |
[백준 11779] 최소비용 구하기2 (Java) - 다익스트라 (0) | 2025.04.18 |
[백준 9466] 텀 프로젝트 (Java) - DFS (3) | 2025.04.17 |