백준 2346번 풍선 터뜨리기: C언어 풀이

백준 2346 풍선 터트리기 문제의 C언어 해설입니다.
큐의 회전을 구현하는 방법과 이에 대한 수학적인 설명을 다룹니다.

전략

큐의 회전 구현하기

1021번 회전하는 큐 문제와 마찬가지로 큐에서 풍선을 POP 하고, 안에 든 숫자만큼 큐를 회전 시켜주면 된다.

숫자가 음수라면 왼쪽으로 회전해야한다. 역시 앞선 문제에서 아이디어를 가져온다.
전체 풍선 수가 10개라면 왼쪽으로 4번 회전 대신 오른쪽으로 6번 회전해주면 된다.
풍선 수에서 좌측 회전 횟수를 빼주면 필요한 우측 회전 횟수가 나온다.

단 단순 뺼셈으로는 곤란한 경우가 있다. 회전 횟수가 전체 풍선 수보다 많은 경우이다.

풍선 수가 10, 쪽지에 적힌 수가 -12인 상황을 생각해보자.
단순히 풍선 수에서 회전 횟수를 빼줄 경우 10 - 12 = -2, 음수가 된다.
실제 필요한 오른쪽 회전 수는 8이다.

머리가 복잡해 지기 전에 수학적으로 생각해보자.
쪽지에 적혀있는 음수를 m, 남아있는 풍선의 수를 n이라고 하자.
m은 대충 다음과 같이 표현할 수 있다.

$$ m = -nq - r, \quad n,q,r \in N,\quad r \lt n$$

필요한 우측 회전 횟수는 n-r 이다.
C에서 m % n 은 -r을 반환한다.
다음과 같이 코드를 짜준다.

movement = (movement > 0) 
            ? (movement - 1) % num_balloons 
            : num_balloons + (movement % num_balloons);

이제 movement 만큼 오른쪽으로 큐를 회전 시키면 된다.
양수일 때 -1을 해준 이유는, 풍선을 pop 하면서 head가 앞으로 한 칸 당겨지기 때문이다.

원형 큐

선형으로 큐를 구현할 시 필요한 배열의 최대 크기는 500500이다.
크키가 좀 큰 것 같아 풍선 최대 개수 보다 큰 2의 거듭제곱, 1024 크기의 배열로 원형 큐를 만들어주었다.

코드

#include <stdio.h>

// Set to 2^n for faster modulo operation
#define QUEUE_SIZE 1024
#define QUEUE_MASK 1023
#define MAX_BALLOON_SIZE 1000

int queue[QUEUE_SIZE];
int head = 0;
int tail = 0;
int balloon_papers[MAX_BALLOON_SIZE];

int main(void)
{
    int num_balloons;
    scanf("%d", &num_balloons);

    // Initialize 
    for (int i = 0; i < num_balloons; i++)
    {
        queue[i] = i + 1;
    }
    tail = num_balloons;

    // Baloon papers have next movement info
    for (int i = 0; i < num_balloons; i++)
    {
        scanf("%d", &balloon_papers[i]);
    }

    while (1)
    {
        // Pop balloon
        printf("%d ", queue[head]);
        int movement = balloon_papers[queue[head] - 1];
        head = (head + 1) & QUEUE_MASK;
        num_balloons--;

        if (num_balloons == 0)
        {
            break;
        }

        // Positivie: Movement -1 since the head moved by popping 
        // Negative: Converted into positive movement
        movement = (movement > 0) 
                    ? (movement - 1) % num_balloons 
                    : num_balloons + (movement % num_balloons);

        // Rotate right by movement
        while (movement != 0)
        {
            queue[tail] = queue[head];
            head = (head + 1) & QUEUE_MASK;
            tail = (tail + 1) & QUEUE_MASK;
            movement--;
        }
    }
}