18.5문제:조세푸스 문제(ID:JOSEPHUS)
문제
1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하느니 차라리 자살하자고 결의했고, 포위당한 N명의 사람들이 모두 원형으로 둘러선 뒤 순서대로 자살하기로 했습니다. 한 사람이 자살하면, 다음에는 그 사람으로부터 시계 방향으로 K번째 살아 있는 사람이 자살하는 것입니다.
조세푸스의 책에 따르면 조세푸스와 다른 병사 하나만이 살아남았을 때 이들은 마음을 바꿔 로마에 항복해서 살아남았다고 합니다. 마지막 두 명 중 하나가 되기 위해서는 조세푸스는 첫 번째 병사로부터 몇 자리 떨어진 곳에 있어야 했을까요?입력
입력의 첫 번째 줄에는 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스는 두 개의 정수 N, K로 주어집니다(3≤N≤1000, 1≤K≤1000).
출력
각 테스트 케이스에 두 개의 정수로, 마지막 살아남는 두 사람의 번호를 오름차순으로 출력합니다. 첫 번째로 자살하는 병사의 번호가 1이며, 다른 사람들의 번호는 첫 번째 병사에서부터 시계 방향으로 정해집니다.
예제 입력
2 6 3 40 3예제 출력
3 5 11 26
First Thoughts
원형배열 아니면 연결리스트
원형배열을 사용할까 연결리스트를 사용할까 고민하였지만 c++의 list라이브러리와 그 안에 이미 구현이 된 많은 함수들을 보고 자신감을 얻어 연결리스트로 작성하였다.
My Code
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
list <int> p;
int N, K;
void suicide() {
int i;
list <int>::iterator it;
for (i = 0; i < N; i++) {
p.push_back(i + 1);
}
it = p.begin();
while (p.size() != 2) {
it=p.erase(it);
for (i = 0; i < K-1; i++) {
if (it == p.end()) {
it = p.begin();
}
it++;
}
if (it == p.end()) {
it = p.begin();
}
}
it = p.begin();
cout << *(it) << " ";
cout<< *(++it) << endl;
}
int main(void) {
int C;
int i;
cin >> C;
for (i = 0; i < C; i++) {
cin >> N >> K;//N명 K번째
suicide();
p.clear();
}
}Answer Code
#include <iostream>
#include <list>
using namespace std;
void josephus(int n, int k) {
list<int> survivors;
for (int i = 1; i <= n; i++) {
survivors.push_back(i);
}
list<int>::iterator kill = survivors.begin();
while (n > 2) {
kill = survivors.erase(kill);
if (kill == survivors.end())
kill = survivors.begin();
--n;
for (int i = 0; i < k - 1; i++) {
++kill;
if (kill == survivors.end())
kill = survivors.begin();
}
}
cout << survivors.front() << " " << survivors.back() << endl;
}
int main() {
int C;
int N, K;
cin >> C;
for (int i = 0; i < C; i++) {
cin >> N >> K;
josephus(N, K);
}
}Difference & Faults
iterator 의 사용
i번째 사람에서 (i+K)번째 사람으로 이동하기 위해서는 iterator+=K를 하면 되는지 알았다. 그런데 에러메시지가 떠서 iterator는 산술연산으로는 안된다는 것을 알았다. 그래서 advance라는 함수를 이용하여 advance(iterator,K)를 하였더니 "cannot increment end list iterator"라고 경고창이 떴다. 그제서야 end라는 예외 경우를 인식하고 end에 도달했을 때 처리하는 방법을 생각했다. 또한 iterator=list.begin()을 사용할 때 list가 채워진 상태에서 호출해야함을 잊지말자.
erase의 사용
erase라는 함수는 처음 사용해보지만 함수 이름만으로도 알 수 있듯이 list의 원소를 삭제하는 기능을 하는 것은 분명했다. 하지만 임의의 원소를 지우고 그 다음 원소를 반환하는지는 몰랐다. 이는 차후에 사용되는 for문에도 영향을 주는 K번 반복한다고 생각했던 것이 K-1번만 순회하면 되는 것이었다.
end일 때 처리방법
나의 코드를 보면 나는 for문을 다 돌고 마지막에 예외처리를 해주었는데 해답 코드처럼 for문의 마지막에 위치하고 erase한 다음에 바로 체크를 해도 좋을 거 같다.
Impressions
c++로 코드를 작성하면서 매번 느끼는 거지만 알고리즘을 풀기 위해서는 c++이 최적의 언어인거 같다. 공부를 하면 할수록 정말 다양한 라이브러리와 함수를 갖고있다. 우리가 일반적으로 생각하고 구현하고 싶은 기능을 가진 함수들은 웬만하면 이미 다 존재하는 거 같다.
Summary
이번 문제는 아이디어도 구현도 가장 쉬웠던 거 같다. 앞으로 남은 단원의 이름을 보면 자료구조의 응용을 다루는 거 같은데 역시 모르고 아무것도 모르고 접하는 거 보다 어느정도 알고 가는 것이 심적으로도 학습적인 면에서도 도움이 되는 거 같다.
