[ 백준 ] 11509 / 풍선 맞추기
# 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 */
Author And Source
이 문제에 관하여([ 백준 ] 11509 / 풍선 맞추기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@gglifer/백준-11509-풍선-맞추기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
/*
* 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 이 적당한 자료구조 인 것 같다
*/
//
// 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 */
Author And Source
이 문제에 관하여([ 백준 ] 11509 / 풍선 맞추기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gglifer/백준-11509-풍선-맞추기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)