1158: 요세푸스 문제

• toc {:toc}

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

출처:https://www.acmicpc.net/problem/1158

풀이

야매 연결리스트 이용(야매 연결리스트가 list보다 더 나을 것 같았음)

1. 야매 연결리스트 형성
2. erase할 때 연결되는 것 이용
3. 끝 범위 일 때(nxt[cursor] != -1) 맨 처음으로 돌아가도록 처리

while문에서 cursor의 이동에 대해 생각해볼 것

// 연결리스트
#include <bits/stdc++.h>
 
using namespace std;
 
const int MX = 10005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;
 
int erase(int addr) {
    nxt[pre[addr]] = nxt[addr];
    if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
    return addr;
}
 
void insert(int addr, int d){
    dat[unused] = d;
    pre[unused] = addr;
    nxt[unused] = nxt[addr];
    if(nxt[addr] != -1) pre[nxt[addr]] = unused;
    nxt[addr] = unused;
    unused++;
}
 
void traverse(){
    int cur = nxt[0];
    while(cur != -1) {
        cout << dat[cur] << ' ';
        cur = nxt[cur];
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    fill(pre, pre+MX, -1);
    fill(nxt, nxt+MX, -1);
    list<int> L = {};
    int N, K;
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        insert(i, i+1);
    }
    cout << "<";
    int cursor = 0;
    while(nxt[0] != -1){
        for (int i = 0; i < K; i++)
        {
            if(nxt[cursor] != -1)
                cursor = nxt[cursor];
            else
                cursor = nxt[0];
        }
        cout << erase(cursor);
        if(nxt[0] != -1)
            cout << ", ";
    }
 
    cout << '>';
    return 0;
}

정답코드

많이 배워야 함을 느낀다….

훨씬 간결함.

원형 연결리스트 형성 방법 익히고 for문 사용의 유동성 익히기

// Authored by : OceanShape
// Co-authored by : -
// http://boj.kr/b7f7b82420c74d43b13c398fc6c73841
#include <bits/stdc++.h>
using namespace std;
 
int N, K, len = 0;
 
// 리스트에서 이전 노드/다음 노드를 가리키는 변수
int pre[5001];
int nxt[5001];
// 요세푸스 순열을 저장하는 변수
vector<int> v;
 
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N >> K;
 
  // 원형 연결 리스트 생성
  // 맨 처음 노드와 마지막 노드가 서로를 가리키도록 지정
  for(int i = 1; i <= N; ++i){
    pre[i] = (i == 1) ? N : i - 1;
    nxt[i] = (i == N) ? 1 : i + 1;
    ++len;
  }
 
  int i = 1;
  // 연결 리스트를 순회하며 순열 생성
  for(int cur = 1; len != 0; cur = nxt[cur]){
    // K 번째일 때 제거
    if(i == K){
      pre[nxt[cur]] = pre[cur];
      nxt[pre[cur]] = nxt[cur];
      v.push_back(cur);
      i = 1;
      --len;
    } else ++i;
  }
 
  // 요세푸스 순열 출력
  cout << "<";
  for(size_t i = 0; i < v.size(); ++i) {
    cout << v[i];
    if(i != v.size() - 1) cout << ", ";
  }
  cout << ">";
}