문제 이해 단계
https://www.acmicpc.net/problem/11509
11509번: 풍선 맞추기
첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다.
www.acmicpc.net
왼쪽부터 오른쪽으로 일렬로 서있는 N개의 풍선이 있다.
그리고 화살은 H의 높이에서 오른쪽으로 출발하고
풍선에 부딪힐 때마다 풍선은 터지며, 화살은 높이가 H-1이 된다.
풍선과 화살은 높이가 같아야 부딪히는 것으로 간주한다.
해당 조건에서 N개의 풍선을 모두 터트릴 때, 가장 적은 화살을 사용해라.
그리고 그 화살의 개수를 출력해라
문제 접근 단계
문제의 조건부터 살펴보면, 풍선의 개수 N와 높이 H는 최대 1,000,000개이다.
만약 높이와 풍선의 개수를 일일이 비교할 일이 있다면,
10^6 * 10^6 = 10^12로 시간초과다.
따라서 완전 탐색은 불가능할 것 같아서 최적화하는 방법을 찾아야 할 것 같다.
풍선을 가장 많이 터트릴 수 있을 때
가장 적은 화살을 사용하려면, 한 번에 많은 풍선을 터트려야 한다.
화살을 어떤 높이에서,
그리고 풍선이 어떤 배열일 때 한 번에 모든 풍선을 터트릴 수 있을까?
H = 5
5,4,3,2,1
간단하게 이렇게 나타날 것이다.
이런 식으로 내림차순으로 연속된 숫자가 있으면 터트리는데 유리하다.
화살을 최소한으로 쏘는 법
우리는 화살을 최소한으로 쏴야 한다.
그러려면 어떻게 해야 할까? 이런 생각을 해봤다.
'굳이 맨 처음에 화살 개수를 정해서 쏴야 하나? 필요할 때마다 쏘면 안 되나?'
만약 필요할 때마다 필요한 만큼만 쏠 수 있다면,
화살의 개수를 최소화할 수 있을 것이다.
여기서 나는 이 문제가 해당 상태에서 최대한의 이득을 보는 그리디 문제라는 것을 깨달았다.
그래서 아래 그림과 같은 과정을 진행했다.
해당 배열로 있는 풍선이 있다고 생각해 보자.
첫 번째 풍선부터 탐색을 한다.
모든 풍선을 터트려야 하기 때문에 첫 번째 풍선부터 터트린다.
첫 번째 풍선을 터트리기 위해서는 H = 3인 화살이 필요하다.
그리고 첫 번째 풍선을 터트리면 H-1으로 값이 2가 된다.
두 번째 풍선도 같은 작용으로 H가 1이 된다.
여기서 세 번째 풍선이 문제다.
기존에 있는 H = 1 짜리 화살로는 높이가 5인 풍선을 터트릴 수 없다.
그렇기 때문에 새로운 H = 5 짜리 화살을 생성해줘야 한다.
이것도 풍선이 터진 후, H-1 = 4가 된다.
위와 같은 과정으로 마지막 풍선까지 다 터트려주면 화살은 0,3 이렇게만 남게 된다.
즉, 화살은 2개만 사용했다는 소리이다.
그러므로 최소 화살의 개수는 2개가 된다.
이런 식으로 알고리즘을 짜서 문제를 풀면 된다.
바로 문제 구현 단계로 가보자.
문제 구현 단계
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int N;
cin >> N;
vector<int> v(N);
for(int i = 0; i < N; i++) cin >> v[i];
vector<int> top; // 화살의 현재 상태를 저장할 벡터
top.push_back(v[0]); // 첫번째 풍선에 따른 H 저장
// 두번째 풍선부터 탐색
for(int i = 1; i < v.size(); i++){
bool success = false;
for(int j = 0; j < top.size(); j++){
// 기존에 화살 - 1과 풍선(첫번째 풍선의 높이를 저장해줘서 -1 해줘야함)
if(top[j] - 1 == v[i]){
success = true;
top[j]--; // 현재 풍선의 높이 저장
// 탈출
break;
}
}
// 기존에 화살 리스트에서 못찾았을 경우 추가해줌
if(!success) top.push_back(v[i]);
}
cout << top.size(); // 화살 벡터의 개수가 답
}코드는 그렇게 길지 않다.
top 벡터가 화살의 개수 및 현재 상태를 저장할 벡터이다.
첫 번째 풍선의 높이를 담았기 때문에 탐색은 두 번째 풍선부터 시작한다.
여기서 주의할 점이 있는데, 풍선의 높이를 저장했기 때문에
(화살 벡터의 저장된 화살 - 1) 이다음 풍선 높이와 같은지 를 비교해줘야 한다.
같다면 다음 풍선의 높이를 저장해 주고, (-1을 해주고) 그 반복문을 탈출한다.
만약 화살 리스트에서 찾을 수 없다면
그 풍선의 높이를 가지고 있는 화살을 새로 만들어준다.
이 반복문이 끝난 뒤, 결국 답은 그 벡터의 사이즈가 된다.
여기까지가 설명의 끝이다. 자세한 것은 주석을 참고하길 바란다.
시행착오
오랜만에 1시간 안에 푼 문제이다.
그리디 문제인데 생각보다 쉬웠다.
그리디 문제는 다른 알고리즘에 비해서 쉬운 편에 속하는 것 같기도 하다.
난이도 기여 쪽에 가보니까 다들 이게 왜 골드?라는 평이 있기도 하더라.
근데 나도 약간 그런 느낌이 들기도 했다.
아이디어 같은 게 쓰이기보다는 구현 느낌이어서..
처음에 구현한 거는 시간초과가 떠서 당황하기는 했다.
근데 거기서 멘탈 잡고 다시 구현한 게 잘한 것 같다.
하도 틀리다 보니 멘탈이 세진 것 같다.
토스아이디
toss.me