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

백준 2346 : 풍선 터뜨리기

 

문제 링크

www.acmicpc.net/problem/2346

2346번: 풍선 터뜨리기

 

 

문제 내용

N개의 풍선이 있다. 각 풍선 안에는 -N부터 N까지의 수가 적혀있는 종이가 들어있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

1. 제일 처음에 있는 1번풍선을 터뜨린다.
2. 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다.
3. 양수가 적혀있을 경우에는 오른쪽으로, 음수가 적혀있을 때는 왼쪽으로 이동한다.

단, 풍선은 원형으로 놓아져있다고 가정한다.

 

ex) N=5

입력 : 3 2 1 -3 -1

출력 : 1 4 5 3 2

 

 

Idea

순서가 있으면서 동적으로 메모리를 할당하고 지울 수 있게 해주는 백터(vector)를 이용해서 풀었다.

+) 구조체를 이용한 linked list로도 풀이가 가능할 듯 하다.

 

 

Code

#include <vector>
#include <iostream>
using namespace std;
 
int main() {
    vector<pair<int, int>> v;
    int N, tmp;
    scanf("%d", &N);
 
    //풍선의 번호와 종이의 숫자 입력
    for (int i = 1; i <= N; i++) {
        scanf("%d", &tmp);
        v.push_back({ i, tmp });
    }
 
    //풍선 터뜨리기
    int idx = 0;
    while (1) {
        //터뜨릴 풍선의 번호를 출력
        printf("%d ", v[idx].first);
 
        //풍선에 있던 종이의 숫자 저장
        int n = v[idx].second;
 
        //풍선 터뜨리기(지우기)
        v.erase(v.begin() + idx);
        
        //남은 풍선이 없다면 break
        if (v.empty()) break;
        
        //종이의 숫자가 양수라면
        if (n > 0) {
            n--;
            idx += n;
            idx = idx % v.size();
        }
        //음수일 때,
        else {
            idx += n;
            if (idx < 0) {
                idx *= -1;
                idx = (v.size() - idx % v.size()) % v.size();
            }
        }
    }
    printf("\n");
    return 0;
}