일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- Algospot
- 누적합
- 그리디
- DFS
- Greedy
- backtracking
- 백트래킹
- 백준
- 문자열
- union-find
- acm
- DP
- 유니온파인드
- 재귀
- stack
- BFS
- BOJ
- 스택
- 알고리즘문제해결전략
- 종만북
- 분리집합
- 분할정복
- 완전탐색
- 동적계획법
- 이분탐색
- 알고스팟
- 세그먼트트리
- 너비우선탐색
- priority_queue
- 다이나믹프로그래밍
- Today
- Total
DAMPER's blog
[ALGOSPOT] 조세푸스 문제 (JOSEPHUS) 본문
출처 : algospot.com/judge/problem/read/JOSEPHUS
algospot.com :: JOSEPHUS
조세푸스 문제 문제 정보 문제 1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하
algospot.com
<문제>
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
연결리스트를 공부할 때 가장 접하기 쉬운 문제이다.
이 문제를 정적배열로 구현하려면 삭제하는 과정에서 문제가 생긴다.
중간에 있는 어떤 element를 1개 삭제한다고 하자. 그 뒤 모든 elements를 -1칸씩 옮겨와야한다.
연결리스트는 동적으로 할당하며, 삭제 시 전 element의 포인터에 삭제하려는 element의 포인터 값을 넣고 메모리를 해제해주면 된다.
이 문제도 linked list의 size가 2가 될 때까지 k칸씩 움직이면서 지워주면 된다.
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
37
38
39
40
|
#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
int tc;
cin>>tc;
while(tc--)
{
int n, k;
cin>>n>>k;
list<int> alist;
for(int i=0;i<n;i++)
alist.push_back(i+1);
list<int>::iterator it = alist.begin();
int next = 0;
while(alist.size()>2)
{
alist.erase(it);
next = (next+k-1)%alist.size();
it = alist.begin();
for(int i=0;i<next;i++)
{
it++;
if(it==alist.end()) it = alist.begin();
}
}
for(auto s : alist)
cout<<s<<' ';
cout<<endl;
}
return 0;
}
|
cs |
'Problem Solving > 알고리즘 문제해결전략' 카테고리의 다른 글
[ALGOSPOT] 외계 신호 분석 (ITES) (0) | 2021.01.23 |
---|---|
[ALGOSPOT] Mismatched Brackets (BRACKETS2) (0) | 2021.01.22 |
[ALGOSPOT] 두니발 박사의 탈옥 (NUMB3RS) (0) | 2021.01.22 |
[ALGOSPOT] 폴리오미노 (POLY) (0) | 2021.01.22 |
[ALGOSPOT] 비대칭 타일링 (ASYMTILING) (0) | 2021.01.22 |