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

 

 

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

2346번: 풍선 터뜨리기

 

1~N번까지 원형으로 풍선이 놓여있다. 풍선 안에는 종이가 들어있다.

1번 풍선 터트리고 안에 있는 종이에 적혀있는 만큼 이동해서 다음 풍선 터트림.

양수면 오른쪽으로, 음수면 왼쪽으로 이동

 

풍선의 index를 꼭 저장해줘야 쉽게 풀 수 있다.

deque 자료구조에 pair를 사용해서 index와 풍선 종이 value를 넣어주고 pop, push 하면 쉽게 풀린다.

 

원형 deque이므로 맨 앞/맨 뒤 원소를 맨 뒤/맨 앞에 넣어주고 pop_front/pop_back을 해서 회전해준다.

그러면 다음 풍선이 맨 앞에 오게되므로 이를 출력해주고, 또 반복해준다.

💡 반복적으로 반복문이 시작되면 맨 앞 원소를 pop 하기 때문에 꼭 dq가 비었는지 확인해주자. 

 

#include <iostream>
#include <deque>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    deque<pair<int, int>> dq; //input index, value
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        dq.push_back({i, a});
    }
    
    while(!dq.empty()){
        //pop-push하면서 맨 앞으로 터트릴 풍선 등장
        cout << dq.front().first + 1  << ' '; //터트릴 풍선 인덱스 출력
        int n = dq.front().second;
        dq.pop_front(); //맨 앞 원소 없앰
        
        if(dq.empty()) return 0; //위에서 맨 앞 원소를 없앴으므로 empty 였는지 확인하기
        
        if(n > 0){ //양수면 오른쪽으로 이동
            for(int i=0; i<n-1; i++){
                dq.push_back(dq.front());
                dq.pop_front();
            }
        }else{ //음수면 왼쪽으로 이동
            for(int i=0; i<-n; i++){
                dq.push_front(dq.back());
                dq.pop_back();
            }
        }
    }   
    return 0;
}