[백준 알고리즘] 1158번: 요세푸스 문제
February 14, 2021
https://www.acmicpc.net/problem/1158
문제
문제
요세푸스 문제는 다음과 같다.
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)
출력
예제와 같이 요세푸스 순열을 출력한다.
풀이
더 깔끔하게 풀 수 있는문제인데 리스트를 사용하려고 하다보니까 요상하게 풀어버렸다. list 컨테이너는 dynamic access가 되지 않는다는 것을 관과하고 풀다가 계속 에러가 나서 뒤늦게 알게 되었다. 그래도 리스트로 풀고 싶어서 시행착오를 조금 거치긴 했지만 풀었다. 핵심이 된는 부분은 erase 했을 때 iterator 포인터가 가르키는 위치가 방금 삭제한 원소의 다음 위치라는 것과 end에 iterator가 도달하게 되면 다시 begin으로 바꾸어주어야 한다는 것이다.
코드
#include <cstdio>
#include <list>
using namespace std;
int main (){
int N, K, idx = 0;
list<int> numbers;
scanf("%d %d", &N, &K);
for (int i = 1 ; i <= N ; i++){
numbers.push_back(i);
}
auto iter = numbers.begin();
int count = 1;
int answer[N];
while(!numbers.empty()){
if(count == K){
answer[idx++] = *iter;
iter = numbers.erase(iter);
count = 0;
iter--;
}
iter++;
if (iter == numbers.end()) iter = numbers.begin();
count++;
}
printf("<");
for (int i = 0 ; i < N ; i++){
if (i == N-1) printf("%d>", answer[i]);
else printf("%d, ", answer[i]);
}
}
