https://www.acmicpc.net/problem/11866
문제
> 요세푸스 문제는 다음과 같다.
> 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다.
> 이제 순서대로 K번째 사람을 제거한다.
> 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.
> 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
> 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.
> 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
> N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성해라.접근
각 단계에서 제거할 사람을 정하기 위해 예제로 주어진 7,3을 통해 쭉 나열해보면 아래와 같다.
1) 3 -> 2번 인덱스
2) 6 -> 4번 인덱스
3) 2 -> 1번 인덱스
4) 7 -> 3번 인덱스
5) 5 -> 2번 인덱스
6) 1 -> 0번 인덱스
7) 4 -> 0번 인덱스
각 인덱스의 규칙을 구해보면 1)은 k번째 사람이니까 인덱스로 따지면 k-1이고, 2)는 1)에 +3번 인덱스를하면 된다.
하지만 2)는 전체 사람의 수가 한명 줄었기 때문에 이를 반영해야한다.
즉, 현재 인덱스가 i라고 할때 다음번 인덱스를 구해보면
i + K(k번째만큼 더해줌) -1(인덱스라서) % 인원수(총 인원수를 넘어가는 경우를 고려) -1(다음 단계에선 한명이 줄어들꺼니까)
따라서 (i+k-1) % size-1이다.
문제해결
> 입력을 N과 K를 받아주고 N까지의 수열을 정수형 벡터 q에 넣어준다.
> 인덱스로 사용할 변수 i를 선언해주고 출력형식에 맞게 꺽쇠괄호를 출력해주고 시작한다.
> 각 단계에서 제거될 수를 구하기 위해 위의 접근에서 얻어낸 수식을 사용한다.
현단계를 통해 다음 단계를 구하기 위해 인원수-1을 했지만
전에 썼던 i의 값이 while문의 다음 연산에 기억되어 이를 사용하면 되므로 현재를 그냥 전 단계에 썼던 i를 끌어와 i를 갱신해주는 형태로 하면된다.
즉, i = (i + K - 1) % q.size(); 이렇게 써주면 된다.
> 이제 출력의 형태로 마지막 출력이 아닌이상 쉼표와 띄어쓰기를 해주고 마지막 출력은 꺽쇠괄호를 닫아준다.
> 제거된 사람을 처리하기 위해 배열에서 지목된 사람(i)값을 제거해준다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N, K;
cin >> N >> K;
vector<int> q;
for (int i = 1; i <= N; i++) q.push_back(i);
cout << "<";
int i = 0;
while (N--)
{
i = (i + K - 1) % q.size();
if (q.size() == 1) cout << q[i] << ">";
else cout << q[i] << ", ";
q.erase(q.begin() + i);
}
}
후기
다 풀고 난 뒤 태그를 보니 큐를 사용하는 문제라고 한다.
원 형태로 꼬리를 무는 식의 문제는 deque를 사용한다고 한다. 이걸 알고나니 예전에 원형테이블에서 식사하는 문제가 생각난다.
deque를 이용해 다시 풀어보자.
