백준 #1021 회전하는 큐

회전하는 큐 문제는 큐의 성질만 잘 이해하면 풀 수 있는 문제라고 보입니다.  정답률도 낮은 번호대 치고는 43%도 괜찮고요.

 

3가지 연산이 가능한 회전하는 큐는, 1. 데이터 뽑아내기, 2. 왼쪽으로 한칸 회전, 3. 오른쪽으로 한칸 회전이 있습니다.

원하는 숫자 위치들을 뽑아낼 때, 2번과 3번의 동작을 최소한으로 하는 문제입니다.  얼듯보면 최적화 문제일 것같지만, 굳이 최적화 문제로 거론될 문제는 아닙니다.

 

문제의 링크는 다음과 같습니다.

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

1021번: 회전하는 큐

 

현재 위치 c 와 뽑아내야할 데이터를 어느쪽으로 돌리면 빨리 갈 수 있는지만 검사하면 됩니다.

 

전 배열을 이용했습니다.

 

최초 N개의 위치에 대한 배열을 0으로 초기화합니다.  그런후 데이터를 뽑을 때마다, 해당 배열 위치에 1로 기록을 합니다.  그런 후에 다음 숫자를 뽑을 때, 현재 위치와 비교하여 어느쪽이 빠른가를 검사합니다.  그 결과를 합산해서 보여주면 됩니다.

 

다음은 제가 작성한 소스입니다.  소스는 참고용으로만 봐주세요.

//------------------------------------------------------------------------------
//  baekjoon #1021 - Rotating Queue
//    - by Aubrey Choi
//    - created at 2019-09-22
//------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
  int n, m, s, c=1, t, ans=0;
  static char v[52];
  scanf("%d%d",&n,&m);
  for(int r=0;r<m;r++)
  {
    scanf("%d",&s);
    for(t=0;c!=s;c=c%n+1) t+=v[c]==0;
    ans += (t<n-r-t)?t:n-r-t; v[c]=1;
  }
  printf("%d\n", ans);
}