[ 백준 ] 2346 / 풍선 터뜨리기

9624 단어 psbojboj

# Appreciation

/*
 * Problem :: 2346 / 풍선 터뜨리기
 *
 * Kind :: Simulation
 *
 * Insight
 * - 예제 입력 1
 *   + 5
 *     3 2 1 -3 -1
 *     # 1번 풍선을 터뜨림, 오른쪽으로 3칸 이동
 *       x 2 1 -3 -1
 *         2 3  4  5  <= 풍선 번호
 *       0 1 2  3
 *     # 4번 풍선을 터뜨림, 왼쪽으로 3칸 이동
 *       x 2 1 x -1
 *         2 3    5
 *         2 1 0  3
 *     # 5번 풍선을 터뜨림, 왼쪽으로 1칸 이동
 *       x 2 1 x x
 *         2 3
 *           1   0
 *     # 3번 풍선을 터뜨림, 오른쪽으로 1칸 이동
 *       x 2 x x x
 *         2
 *         1 0
 *     # 2번 풍선을 터뜨림, 풍선이 더이상 없으므로 종료
 *
 * - 푸는 방법은 크게 2가지일 것 같다
 *   + 첫 번째, 터진 풍선의 위치를 저장하기
 *     # (bool) isDeleted[N] 으로 터진 풍선의 위치를 저장해서
 *       터지지 않은 풍선으로 이동할 때만 이동가능한 횟수를 줄여주고
 *       이동가능한 횟수가 0 이 되면 멈춘다
 *       -> 이때 멈춘 자리가 다음에 터뜨릴 풍선의 위치이다
 *          => 터진 풍선위 위치를 매번 방문해야 되어 비효율적이다
 *   + 두 번째, 터진 풍선의 위치를 없애버리기
 *     # Vector 의 erase 연산을 사용해서 터진 풍선의 위치를 없애준다
 *       Vector 에는 터지지 않은 풍선만 남아있으므로 이동할 때마다 이동가능 횟수가 줄어든다
 *       -> 이때도 멈춘 자리가 다음에 터뜨릴 풍선의 위치이다
 *          => 풍선을 터뜨린 위치는 자연스레 1칸 오른쪽의 터지지 않은 풍선의 위치가 된다
 *             오른쪽으로 이동해야 되는 경우, 1칸을 이미 이동한 것이 되어버렸기에
 *             이를 고려해야 한다
 *
 * Point
 * - 다음 풍선을 터뜨릴 위치를 알아낼 때
 *   idx %= B.size()
 *   로 해서 한참동안 헤맸다...
 *   + Vector 의 size 연산의 결과는 unsigned long 인데
 *     idx 가 음수인 경우 이를 양수로 만들어버려서 계속 오답이 나왔던 것이다...
 *     # 3시간 동안 로직이 틀렸나 싶었는데 이게 문제였다는 것을 알았을 때 느껴졌떤 그 허탈감이란...
 *       -> 역시 기본기가 중요하다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>

using namespace std;

#define endl '\n'

// Set up : Global Variables
struct Balloon { int no, num; };

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    vector<Balloon> B(N);
    for (int i=0; i<N; i++) {
        cin >> B[i].num;
        B[i].no = i+1;
    }

    // Process
    int idx = 0; /* 풍선을 터뜨릴 위치 */
    vector<int> A; /* 터진 풍선의 번호가 저장된 Vector */
    while (true) {
        int num = B[idx].num; /* 터뜨릴 풍선에 적혀있는 수 */
        A.push_back(B[idx].no); /* 터뜨릴 풍선의 번호를 저장 */
        B.erase(B.begin()+idx); /* 풍선을 터뜨림 */
        if (B.empty()) break; /* 남아있는 풍선이 없다면 종료 */

        int s = B.size(); /* 남은 풍선의 개수 */
        /* 적혀있는 수가 양수이면, 오른쪽으로 이동해야하는데
         * 풍선이 터지면서 현재 위치가 오른쪽으로 1칸 이동한 것이 되어버렸기에
         * 이를 고려해주어야 함 */
        if (num > 0) num--;
        /* 참고로 적혀있는 수가 음수이면, 왼쪽으로 이동해야하는데
         * 풍선이 터지면서 현재 위치는 오른쪽으로 1칸 이동한 것이 되어버렸지만
         * 왼쪽으로는 0칸 이동한 것이 되어
         * 고려치 않아도 상관없음 */
        idx += num;
        idx %= s;
        if (idx < 0) idx += s;
    }

    // Control : Output
    for (int no : A) {
        cout << no << ' ';
    }
}

// Helper Functions
/* None */

좋은 웹페이지 즐겨찾기