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

 

풀이

#include <iostream>
#include <deque>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin.tie(NULL);

    int N;
    cin >> N;

    deque<pair<int, int>> dq;
    for( int i = 1; i <= N; ++i ){
        int dq_num;
        cin >> dq_num;
        dq.push_back(make_pair(i, dq_num));
    }

    cout << dq.front().first << " ";
    int tmp = dq.front().second;
    dq.pop_front();
    while(!dq.empty()) {
        if( tmp > 0 ) {
            tmp--;
            for( int i = 0; i < tmp; ++i ) {
                dq.push_back(dq.front());
                dq.pop_front();
            }
            cout << dq.front().first << " ";
            tmp = dq.front().second;
            dq.pop_front();
        }
        else {
            tmp++;
            for( int i = 0; i > tmp; --i ) {
                dq.push_front(dq.back());
                dq.pop_back();
            }
            cout << dq.back().first << " ";
            tmp = dq.back().second;
            dq.pop_back();
        }

    }



    return 0;
}

1) 풍선의 번호, 풍선 안에 들어있는 쪽지의 값이 있으므로 pair<int(풍선의 번호), int(쪽지의 값)>로 저장하는데, 쪽지에 들어있는 값이 양수, 음수 둘 다 존재하므로 deque로 저장한다.
- deque로 저장하는 이유는 뒤에서 설명하겠다.

2) while문에서 dq가 empty하지 않은 동안 반복한다.
-1} 풍선은 하나씩 터지므로 쪽지의 값이 1인 경우는 터진 풍선의 바로 오른쪽 풍선을 터트리는 것이다. 반대로 -1인 경우는 터진 풍선의 바로 왼쪽 풍선을 터트리는 것이다, 따라서 tmp로 쪽지의 값이 양수인 경우 1을 뺀 값, 음수인 경우 1을 더한 값을 저장한다. 
-2} 쪽지의 값이 양수인 경우 앞에 존재하던 값이 뒤로 밀리기 때문에 front()를 back()으로 옮기고 쪽지의 값이 음수인 경우 뒤에 존재하던 값이 앞으로 땡겨지기 때문에 back()을 front()로 옮긴다.