글 읽기 - 회전하는큐 반례 부탁드립니다.

keepyourweaponaimed 4년 전 0

질문 게시판들을 정독한 뒤에 얻어진 반례들을 대입해봤고 전부 성공적으로 아웃풋이 나왔습니다.

9 5
5 1 4 2 3
> 12
9 6
6 5 4 1 3 2
> 11
5 5
4 1 5 3 2
> 5
10 8
7 6 2 1 3 8 5 4
> 14
9 8
3 4 6 1 2 8 5 7
> 9
10 10
4 9 1 7 2 3 10 6 8 5
> 15
8 7
7 3 4 6 1 5 2
> 9
10 4
3 1 4 2
> 6

제가 짠 로직 자체도 몇번이고 머릿 속으로 생각해봤는데 어느 부분에서 틀렸는지 가늠이 잘 가지 않습니다.

반례 알려주시면 감사하겠습니다.

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int main(){
  int N, m;
  scanf("%d %d", &N, &m);
  deque<int> dq;
  deque<int> v;
  for(int i=1; i<=N; i++) dq.push_back(i);
  for(int i=0; i<m; i++) {
    int aa;
    scanf("%d", &aa);
    v.push_back(aa);
  }
  int cnt = 0;
  while(v.size()){
    int idx;
    for(int i=0; i<N; i++){
      if(dq[i] == v.front()) idx = i;
    }
    if(dq.size() / 2 > idx -1 ){
      if(dq.front() == v.front()) dq.pop_front();
      else{
        while(dq.front() != v.front()){
          cnt++;
          int tmp = dq.front();
          dq.pop_front();
          dq.push_back(tmp);
        }
        dq.pop_front();
      }
      v.pop_front();
    }else{
      if(dq.front() == v.front()) dq.pop_front();
      else{
        while(dq.front() != v.front()){
          cnt++;
          int tmp = dq.back();
          dq.pop_back();
          dq.push_front(tmp);
        }
        dq.pop_front();
      }
      v.pop_front();
    }
  }
  printf("%d", cnt);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

회전하는큐 반례 부탁드립니다.

keepyourweaponaimed 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말