[ 백준 ] 11509 / 풍선 맞추기

7229 단어 psbojboj

# Appreciation

/*
 * Problem :: 11509 / 풍선 맞추기
 *
 * Kind :: Greedy
 *
 * Insight
 * - 예제 입력 1
 *   5
 *   2 1 5 4 3
 *   + 1 번째 풍선 [높이 2]
 *     높이 2인 풍선을 터뜨릴 수 없다 --- 쏜 화살이 없음
 *     따라서, 높이 2인 풍선을 터뜨릴 화살을 쏜다
 *     이 화살은 높이 2인 풍선을 터뜨린 후 높이 1이 된다
 *   + 2 번째 풍선 [높이 1]
 *     높이 1인 풍선을 터뜨릴 수 있다 --- 높이 1인 화살이 있음
 *     이 화살은 높이 1인 풍선을 터뜨린 후 높인 0이 된다 (바닥에 떨어진다)
 *   + 3 번째 풍선 [높이 5]
 *     높이 5인 풍선을 터뜨릴 수 없다 --- 높이 0인 화살밖에 없음
 *     따라서, 높이 5인 풍선을 터뜨릴 화살을 쏜다
 *     이 화살은 높이 5인 풍선을 터뜨린 후 높이 4가 된다
 *   + 4 번째 풍선 [높이 4]
 *     높이 4인 풍선을 터뜨릴 수 있다 --- 높이 4인 화살이 있음
 *     이 화살은 높이 4인 풍선을 터뜨린 후 높이 3이 된다
 *   + 5 번째 풍선 [높이 5]
 *     높이 3인 풍선을 터뜨릴 수 있다 --- 높이 3인 화살이 있음
 *     이 화살은 높이 3인 풍선을 터뜨린 후 높이 2가 된다
 *
 * - 풍선의 높이가 h 일 때, 높이 h 인 화살이 있는지 없는지 알아내면 된다
 *   있다면? 그 n(높이 h 인 화살) -= 1 AND n(높이 h-1 인 화살) += 1
 *   없다면? 쏜 화살의 개수 +=1 AND n(높이 h-1 인 화살) += 1 <= 풍선을 터뜨린 후 높이 1 감소
 *   + 그때 그때 특정 높이의 화살의 개수를 알아내는 거라면
 *     Map 이 적당한 자료구조 인 것 같다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <map>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    int H[N];
    for (int i=0; i<N; i++) {
        cin >> H[i];
    }

    // Process
    map<int,int> arrows; /* arrows[h] = 높이 h 인 화살의 개수 */
    int ans = 0; /* 쏜 화살의 개수 */
    for (int i=0; i<N; i++) {
        int h = H[i];
        if (arrows[h] > 0) { /* 높이 h 인 화살이 있다면 */
            arrows[h]--; /* 그 중 한 화살이 풍선을 터뜨림 */
            arrows[h-1]++; /* 풍선을 터뜨린 화살은 높이 1 감소 */
        } else {
            ans++; /* 높이 h 인 화살이 없다면 풍선을 터뜨리기 위한 화살을 새로 쏨 */
            arrows[h-1]++; /* 쏜 화살은 풍선을 터뜨리고 높이 1 감소 */
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */

좋은 웹페이지 즐겨찾기