[백준/C++] 2346번 : 풍선 터뜨리기

 

 

풀이

• 각 풍선의 값을 덱에 값, 풍선 번호 쌍으로 저장한다. 이떄 풍선번호는 1~N까지 순서로 진행된다.
• 현재 풍선의 값을 cur에 저장하고, 해당 풍선의 번호를 출력한다.
• 현재 풍선은 이미 터진 것으로 처리하고, 덱에서 제거한다.
• cur이 양수인 경우: cur-1만큼 덱의 앞부분을 뒤로 옮긴다. cur-1번만큼 이동
• cur이 음수인 경우: -cur번만큼 덱의 뒷부분을 앞으로 옮긴다. cur번만큼 음수값으로 이동
• 풍선을 모두 터뜨린 후에는 풍선의 번호를 출력한다. 번호는 터뜨린 순서대로 출력된다.

 

 

•  

코드

#include <iostream>
#include <deque>

using namespace std;

deque<pair<int, int>> dq;
int N;

int main(void) {
    cin >> N;
    int num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        dq.push_back(make_pair(num, i + 1));
    }

    while (!dq.empty()) {
        int cur = dq.front().first;
        cout << dq.front().second << " ";
        dq.pop_front();

        if (cur > 0) { // 양수인 경우
            while (cur > 1) {
                dq.push_back(dq.front());
                dq.pop_front();
                cur--;
            }
        } else { // 음수인 경우
            cur = -cur;
            while (cur > 0) {
                dq.push_front(dq.back());
                dq.pop_back();
                cur--;
            }
        }
    }

    return 0;
}

 

 

 

 

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

2346번: 풍선 터뜨리기