백준 11509 풍선 맞추기(C++)

https://www.acmicpc.net/problem/11509

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr;
vector<int> arrow;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    arr.resize(n);


    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    arrow.push_back(arr[0]);

    // 두번째 풍선부터 탐색
    for(int i = 1; i < arr.size(); i++){
        bool success = false;
        for(int j = 0; j < arrow.size(); j++){
            // 기존에 화살 - 1과 풍선(첫번째 풍선의 높이를 저장해줘서 -1 해줘야함)
            if(arrow[j] - 1 == arr[i]){
                success = true;
                arrow[j]--; // 현재 풍선의 높이 저장
                // 탈출
                break;
            }
        }
        // 기존에 화살 리스트에서 못찾았을 경우 추가해줌
        if(!success) arrow.push_back(arr[i]);
    }
    cout << arrow.size();

    return 0;
}

1. 문제

n개의 풍선의 높이가 일렬로 주어진다. 왼쪽에서 다트를 던져 풍선을 터뜨리려는데, 다트는 풍선을 맞출 때 마다 높이가 1씩 줄어든다. 

5
2 1 5 4 3

위의 예제가 주어졌을 때, 5의 높이, 2의 높이로 각각 던져서 풍선을 모두 터뜨릴 수 있다. 다트의 개수를 최소로 하여 풍선을 모두 터뜨리려 할 때, 그 다트의 개수를 구하라.

2. 풀이

 첫 다트를 던지고, 다트가 필요할 때 마다 새로운 다트를 던지는 식으로 하여 그리디하게 풀 수 있다.

    arrow.push_back(arr[0]);

 우선 맨 왼쪽에 있는 높이의 풍선은 무조건 같은 높이의 다트를 던져야 맞출 수 있으므로 던진다.

    // 두번째 풍선부터 탐색
    for(int i = 1; i < arr.size(); i++){
        bool success = false;
        for(int j = 0; j < arrow.size(); j++){
            // 기존에 화살 - 1과 풍선(첫번째 풍선의 높이를 저장해줘서 -1 해줘야함)
            if(arrow[j] - 1 == arr[i]){
                success = true;
                arrow[j]--; // 현재 풍선의 높이 저장
                // 탈출
                break;
            }
        }
        // 기존에 화살 리스트에서 못찾았을 경우 추가해줌
        if(!success) arrow.push_back(arr[i]);
    }

 그 후 두 번째 풍선부터, 다트의 높이를 찾아가며 기존 다트의 높이에서 1을 빼면 현재 풍선의 높이가 나오는 지 확인한다.(다트는 전 풍선을 맞추기 이전의 높이가 저장되어 있으므로)  해당 풍선을 찾았다면 그 다트는 높이가 1 낮아지게 된다. 만약 모든 다트를 확인했음에도 해당 풍선을 터뜨릴 다트를 찾지 못했다면 해당 풍선의 높이에 해당하는 다트를 새로 던진다.

 

    cout << arrow.size();

 모든 연산이 끝나면 arrow 배열에는 각 다트의 높이가 저장되어 있을 것이다. 해당 벡터의 크기를 출력하면 다트의 개수, 정답을 구할 수 있다.