[KOITP] 풍선

출    처 : http://koitp.org/problem/SDS_PRO_6_4/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	1644	385 (23%)	343

문제

큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다. 진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다.

높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.

우리의 목표는 모든 풍선을 터트리되 가능한한 적은 화살을 사용하는 것이다.

입력

첫 번째 줄에는 정수 N(1 ≤ N ≤ 1 000 000)이 들어온다.

두 번째 줄에는 배열 Hi가 N개 들어온다.

각각의 Hi(1 ≤ Hi ≤ 1 000 000)는 i번째 풍선의 높이에 해당하며 왼쪽에서 오른쪽으로 나열되는 순서이다.

출력

첫번째 줄 한줄에 최소한 필요한 화살의 갯수를 출력한다.

힌트

예제 입력 1

5
2 1 5 4 3

예제 출력 1

2

예제 입력 2

5
1 2 3 4 5

예제 출력 2

5

예제 입력 3

5
4 5 2 1 4

예제 출력 3

3

< Comment >

 문제자체는 그다지 어렵지 않았는데, 그리디 알고리즘에 대해서 생각하는 경우는 별로 없다보니 시간이 걸린 것 같습니다, 기본 아이디어는 맨 앞의 풍선을 터트리기 위해서는 반드시 화살을 쏴야만 하므로, 맨앞에서부터 차례대로 현재 위치의 화살을 추가해 주는 것입니다. 그리고 화살이 현재 풍선의 높이에 있다면, 이를 터트린 후, 1 만큼 낮은 높이의 화살을 추가하고, 만약 없다면 화살을 추가해 줍니다. 이 아이디어를 기본으로 하여 앞에서부터 풀면 됩니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Balloon {
	
	public static int N = 0;
	public static int INF = Integer.MAX_VALUE;
	
	public static int H[] = null;
	public static int Hcount[] = null;

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		H = new int[N + 1];
		
		int maxHeight = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1 ; i <= N ; i++) {
			H[i] = Integer.parseInt(st.nextToken());
			maxHeight = Math.max(maxHeight, H[i]);
		}
		
		Hcount = new int[maxHeight + 1];
		int answer = 0;
		for (int i = 1 ; i <= N ; i++) {
			if(Hcount[H[i]] > 0) {
				Hcount[H[i]]--;
				Hcount[H[i] - 1]++;
			} else {
				Hcount[H[i] - 1]++;
				answer++;
			}
		}
		
		bw.write("" + answer);
		bw.flush();
		bw.close();
	}
}