[BOJ] #1021 회전하는 큐

시간 제한	메모리 제한	정답 비율
2 초	128 MB	43.582%

 

1021번: 회전하는 큐

 

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

해결

단순 구현으로 head를 처음 시작 위치로 보았고, 각각 왼쪽으로 회전할 때, 오른쪽으로 회전할 때를 함수 func 의 두 번째 인자 dir로 구분하여서 0 이면 3번 연산 1 이면 2번 연산을 의미한다. 각각 방향에서 뽑아내려고 하는 수의 위치까지의 거리를 비교하여 더 짧은 방향을 선택한다. 선택할 때는 chk 배열에 1로 나타내고, head를 이동시켰다.

 

코드

메모리	시간
1984 KB	0 ms

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef pair<int, int> p;
int n, m, pos[55], arr[55], chk[55], head=0, ans;
p func( int next, int dir) {
    int cnt = 0, headCopy = head;
    int d = dir ? 1 : n - 1;
    while ( arr[headCopy] != next) {
        headCopy = (headCopy + d) % n;
        if (chk[headCopy]) continue;
        cnt++;
    }
    return { cnt , headCopy };
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &pos[i]);
    }
    for (int i = 0; i < n; i++) arr[i] = i;
 
    for (int i = 0; i < m; i++) {
        int next = pos[i] - 1, cnt;
        if (head == next) {
            chk[head] = 1;
            cnt = 1;
            int flg = 0;
            for (int j = 0; j < n; j++)
                if (!chk[j]) flg = 1;
            if (flg) {
                while (chk[(head + cnt) % n]) cnt++;
                head = (head + cnt) % n;
            } 
            continue;
        }
 
        p left = func(next, 0);
        p right = func(next, 1);
        if (right.first < left.first) {
            ans += right.first;
            chk[right.second] = 1;
            cnt = 1;
            while (chk[(right.second + cnt) % n]) cnt++;
            head = (right.second + cnt) % n;
        }
        else {
            ans += left.first;
            chk[left.second] = 1;
            cnt = 1;
            while (chk[(left.second + cnt) % n]) cnt++;
            head = (left.second + cnt) % n;
        }
    }
    printf("%d", ans);
    return 0;
}

 

멋진 방법

열심히 고민해서 코드를 짰다고 생각했지만 맞은 사람 코드를 보니 더 좋은 아이디어가 있었다.

#include <stdio.h>
int n, m, i, k, c, a[99];
int main() {
    scanf("%d%d", &n, &m);
    for (i = 0; i < m; i++)
        scanf("%d", &a[i]), a[i]--;
    for (i = 0; i < m; i++) { 
        c += a[i] > n-- / 2 ? n + 1 - a[i] : a[i]; 
        for (k = i + 1; k < m; k++)
            a[k] = (a[k] - a[i] + n) % (n + 1) % n; 
    }
    printf("%d\n", c);
}