[백준] 11866.cpp : 요세푸스 문제 0

www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

#include <cstdio>
#include <vector>

using namespace std;

int main(void)
{
  int n, k;
  int ans, at = 0;

  scanf("%d %d", &n ,&k);

  // 벡터를 최대갯수인 1000개 설정해놓고 초기화
  vector<int> v(1000);
  for(int i = 0 ; i < n ; i++)
  {
    v[i] = i + 1;
  }

  int curSize = n;
  printf("<");
  // 1명 남을때까지 반복, 마지막 1명은 끝나고 출력
  while(curSize > 1)
  {
    // at 은 이번 반복 때 제거할 사람을 가리킨다
    // k - 1 을 더하는 이유는 이전 at 을 가리키던 사람이 지워지기 때문에,
    // 지워졌던 사람까지 포함하여 생각하기 위해서이다
    at += k - 1;
    // 가리키는 위치가 전체 사람 수를 넘어갈 경우,계속 앞으로 돌려보낸다
    while(at >= curSize)
    {
      at -= curSize;
    }
    ans = v[at];

    // 지워준다
    v.erase(v.begin() + at);

    printf("%d, ", ans);
    curSize--;
  }
  printf("%d>\n", v[0]);
}

[Try]

1. 맨 뒤와 맨 앞에 원 모양으로 연결된 형태를 사용해서 매번 3칸 뒤로 간다음 해당 값을 출력하고 연결을 끊어주는 식으로 할 수 있을

     것 같은데 다 구현하기 귀찮으니 적당한 패턴을 파악

 

[Point]

1. 로직을 생각해내는데는 금방 걸렸지만, 정확한 위치의 인덱스를 설정하는데 애 좀 먹었다.

2. 큐를 사용했다? 1부터 n 까지 넣어놓고, k 번만큼 앞에서 빼고 뒤로 넣어주는 형식인데 생각지도 못했다. 적절한 자료구조를 생각해

     내는 법은 언제쯤 습득할까

3. 위의 방식을 사용해도 0ms 인 걸 보면서 push 와 pop 의 시간복잡도가 O(1) 이라는 걸 다시 한번 느꼈다.

 

[More]

1. 원형 링크드리스트