백준 2346 풍선 터뜨리기

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

2346번: 풍선 터뜨리기

#include <iostream>
#include <queue>


using namespace std;

int main() {

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

    int n;
    deque<pair<int, int>> q;        //{풍선 안 종이에 적힌 번호, 풍선의 번호}

    cin >> n;

    for (int i = 1; i <= n; i++) {
        int temp;
        cin >> temp;

        q.push_back(make_pair(temp, i));
    }

    while (!q.empty()) {

        pair<int, int> cur = q.front();


        cout << cur.second<<" ";

        q.pop_front();

        if(q.empty()) break;
        //양수일 경우 오른쪽으로 이동
        if (cur.first > 0) {
            for (int i = 0; i < cur.first - 1; i++) {
                q.push_back(q.front());
                q.pop_front();

            }
        }
        //음수일 경우 왼쪽으로 이동
        else {
            for (int i = 0; i > cur.first; i--) {
                q.push_front(q.back());
                q.pop_back();

            }
        }


    }



    return 0;
}

 

요제푸스 문제에 양방향으로 이동하므로 deque를 사용하여 풀 수 있다.

deque에 {풍선 안의 종이에 적힌 번호, 풍선의 번호}를 pair로 받아 넣고

터뜨려야 할 풍선의 번호를 출력하고 pop한다.

그 후 모든 풍선이 터질 때 까지 해당 종이의 숫자만큼

풍선의 종이 번호가 양수이면 front에서 꺼내 back에, 음수이면 back에서 꺼내 front에 집어넣는다.

다만 양수일 경우에는 처음 풍선이 터질 때 pop하므로 cur.first-1 만큼만 반복문을 돌린다.