728x90
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); } | cs |
3. 문제 출처 |
https://www.acmicpc.net/problem/11866
4. 참고 |
구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.620~622.
iterator에 대해 https://eehoeskrap.tistory.com/263
'<백준> > |c++| normal' 카테고리의 다른 글
[c++] 백준 1021 - 회전하는 큐(디큐, 반복자(iterator)) (0) | 2019.04.01 |
---|---|
[c++] 백준 10866 - 덱 사용하기(deque, 덱, 원형 덱?) (0) | 2019.04.01 |
[C++] 백준 1966 - 프린터 큐(priority_queue) (0) | 2019.03.31 |
[C++] 백준 2504 - 괄호의 값 (0) | 2019.03.14 |
[C++] 백준 9012 - 괄호(스택 활용) (0) | 2019.03.14 |