[c++] 백준 11866 - 조세퍼스 문제 0(포인터, 리스트)

0. 주어진 문제

조세퍼스 문제 0 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	5837	3331	2905	59.346%

문제

조세퍼스 문제는 다음과 같다.

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 ≤ 1,000)

출력

예제와 같이 조세퍼스 순열을 출력한다.

1. 풀이

1) list를 활용하여 구현하였다.

2) iterator을 이용해서 이번에 죽는 사람을 출력시켰다.( *iterator을 사용하면 iterator가 가리키는 주소의 값을 가져올 수 있었다.)

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include<iostream> #include<list> using namespace std;   void josephus(int n, int k) {     cout << "<";     std::list<int> survivors;     for (int i = 1; i <= n; i++) survivors.push_back(i);     //이번에 죽을 사람을 나타내는 포인터     std::list<int>::iterator kill = survivors.begin();     for (int i = 1; i < k; i++) {         kill++;     }     while (n > 1) {         //첫째 사람이 자살한다. erase()는 지운 원소의 다음 원소를 반환한다.         --n;         cout << *kill <<", ";         kill = survivors.erase(kill);         if (kill == survivors.end()) kill = survivors.begin();                  //k-1번 다음 사람으로 옮긴다.         for (int i = 0; i < k - 1; ++i) {             ++kill;             if (kill == survivors.end()) kill = survivors.begin();         }         if (n <= 1) break;     }     cout << *kill << ">\n"; }   int main() {     int n, k;     std::cin >> n >> k;       josephus(n, k); } Colored by Color Scripter

cs

3. 문제 출처

https://www.acmicpc.net/problem/11866

4. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.620~622.

iterator에 대해 https://eehoeskrap.tistory.com/263