알고리즘 문제해결 전략 Chapter 18 - JOSEPHUS(C++)

madpotato1713·2019년 12월 30일
0

알고리즘

목록 보기
10/76

예제: 조세푸스 문제

문제
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

풀이

문제 내용이 ㄷㄷㄷ😱 자살과 배신이라니.. 무서운 문제다.

문제 자체는 list만 쓸 줄 알면 크게 어렵지는 않은 것 같다. 내가 재귀함수 타입이 아닌건지.. 같은 난이도 하 문제인데 느낌이 많이 다른 것 같다.

물론 C언처럼 ListNode 구조체를 직접 만들어서 linked list를 만든다면 어려운 문제가 되겠지..만! C++의 장점을 적극 활용하고자 한다😁

다른 문제들하고 다르게 별다르게 코멘트 할 것이 없다.
list에 N 개수만큼 숫자를 오름차순으로 집어넣어서, K만큼 뛰어넘으면서 2개가 남을때까지 삭제해주면 된다.

주의할점은, C++의 list는 circular linked list가 아니기 때문에, iterator가 리스트의 end() 위치에 다다랐을 때 begin()으로 바꿔주어야 한다는 것이다.

전체적인 소스코드는 아래와 같다.

소스 코드

#include<iostream>
#include<list>

using namespace std;

int N, K;

void solve() {
	
	list<int> mem;
	for (int i = 1; i <= N; i++) {
		mem.push_back(i);
	}
	list<int>::iterator itr = mem.begin();

	while (N > 2) {
		itr = mem.erase(itr);
		N--;
		if (itr == mem.end()) {
			itr = mem.begin();
		}

		for (int i = 1; i < K; i++) {
			itr++;
			if (itr == mem.end()) {
				itr = mem.begin();
			}
		}
	}

	for (auto x : mem) {
		cout << x << " ";
	}
	cout << endl;
}

int main() {

	int testCase;
	cin >> testCase;

	for (int tc = 0; tc < testCase; tc++) {
		cin >> N >> K;

		solve();
	}

	return 0;
}

풀이 후기

물론 난이도 하 문제라 그렇지만, list문제를 작정하고 내면 토나오는것을 알고있다.🤮
한번 잡은 기초개념은 놓치지 말자!

profile
개발자 성장일기

0개의 댓글