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

문제

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

• 소요 시간 : 35분
• 난이도 : 실버 3

접근 방법

구현을 이용하였다.

 

1. N 사이즈의 정수 배열에 입력받은 풍선 안의 수를 저장한다. (0 ~ N-1)

2. 이동하는 함수를 만든다. 

- 풍선의 번호에 따라 방향을 지정한다.

- 풍선 안의 수만큼 while문을 통해 이동한다.

   - 풍선이 터져있는 경우 세지 않는다.

   - N보다 커지면 안되므로 나머지 연산을 이용한다.

   - 0보다 작아지면 안되므로 0보다 작을 경우 N-1로 이동한다.

3. N만큼 이동하여 모든 풍선을 터트린다.

나의 풀이

#include <iostream>


using namespace std;

int balloons[1000];
int N;

int moveIdx(int idx, int num) {
    int cnt = 0;
    int dir = 1; // 오른쪽
    if (num < 0) dir = -1; // 왼쪽 

    while(cnt < abs(num)) {

        idx = (idx + dir) % N;   
        if (idx < 0) idx = N-1;    

        if (balloons[idx] != 0) cnt++;

    }


    return idx;
}


int main() {

    cin >> N;

    int num;
    for(int i=0; i<N; i++) {
        cin >> num;
        balloons[i] = num;
    }

    int idx = 0;

    for(int i=0; i<N-1; i++) {
        cout << idx + 1 << " ";
        int num = balloons[idx];    
        balloons[idx] = 0;
        idx = moveIdx(idx, num);
    }

    cout << idx + 1 << " ";


    return 0;
}

 

정리

구현으로 풀었지만 다른 사람들의 풀이를 보니 덱을 사용하여 푸는 방법도 있어 그렇게도 풀어봐야겠다.