백준[11509] - 풍선 맞추기

• 문제: https://www.acmicpc.net/problem/11509
• 분류: 그리디
• 난이도: G5
• 소요시간: 40m
• 자아성찰:
  • 그리디, DP는 여전히 어렵다.
  • 왼쪽에서 오른쪽으로만 화살을 쏠 수 있다는 조건을 통해 그리디 문제인 걸 알았다.
  • 현재 위치에서 반드시 풍선을 터뜨려야 한다.
  • 배열의 index를 풍선 높이로, index의 값을 해당 높이에 남아있는 화살 수로 접근했다.
  • 현재 위치의 풍선 높이에 해당하는 화살이 존재한다면 (arr[H] > 0), 해당 화살은 사라지고(arr[H] --) 높이 - 1의 화살이 생긴다. (arr[H - 1]++)
  • 현재 위치의 풍선 높이에 해당하는 화살이 존재하지 않는다면(arr[H] = 0) 새 화살을 쏘고 높이 - 1의 화살이 생긴다. (arr[H - 1]++)
  • 그리디는 항상 코드는 단순하지만 접근이 어렵다.. 

11509번: 풍선 맞추기

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B_11509 {

    private static int N, result = 0;
    // 풍선 높이는 최대 100만
    private static int[] arr = new int[1_000_001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            // 현재 위치의 풍선 높이 H
            int H = Integer.parseInt(st.nextToken());
            // 현재 높이에 화살이 남아있다면
            if (arr[H] > 0) {
                // 화살 사용
                arr[H]--;
            }
            // 현재 높이에 화살이 남아있어서 그 화살을 썼든, 화살이 없어 새 화살을 쐈든 H - 1 높이에는 화살이 하나 생긴다.
            arr[H - 1]++;
        }
        
        // 각 높이에 남아있는 화살 수의 합을 구한다. (쏜 화살 수)
        for (int i : arr) {
            result += i;
        }
        System.out.println(result);
    }
}