알고리즘
[Java] 백준 11509번 풍선 맞추기
J3SUNG
2023. 8. 9. 00:52
728x90
그리디 문제입니다.
최소의 화살을 사용해서 풍선을 터트려야 합니다.
풍선의 높이가 주어지고 화살은 직선으로 이동합니다.
화살이 풍선과 닿으면 풍선은 터지고 화살의 높이가 한칸 내려갑니다.
1_000_002 크기의 배열을 만들었습니다.
풍선의 높이가 입력으로 들어오면 해당 높이 + 1에 풍선이 있는지 확인합니다.
- 있으면 해당 높이에 -1을 하고 현재위치에 +1을 합니다.
- 없으면 현재위치에 +1을 합니다.
모든 풍선에 위의 과정을 반복해주고 배열안에 값들의 합을 출력해주었습니다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = null;
int result = 0;
int n = Integer.parseInt(br.readLine());
int[] arr = new int[1000002];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; ++i) {
int num = Integer.parseInt(st.nextToken());
if (arr[num + 1] > 0) {
--arr[num + 1];
}
++arr[num];
}
for (int i = 0; i < arr.length; ++i) {
result = arr[i] > 0 ? result + arr[i] : result;
}
bw.write(result + "\n");
bw.close();
}
}