[BOJ] 백준 #1158. 요세푸스 문제 (C++)

🎨 문제

문제 링크: https://www.acmicpc.net/problem/1158

• 알고리즘 분류: ___
• 난이도: Silver Ⅴ

💬 풀이

구현이 꽤 까다로웠던 문제.

1. 일단 벡터에 1~N까지 넣고
2. i=K부터 시작해서 제거한다.
   👉🏻 제거는 값을 0으로 바꿔주는 것으로 처리. v[i] = 0
   👉🏻 이때 i가 N을 넘냐 안넘냐에 따라 인덱스 표현을 달리 해줘야 함
3. 다음으로 남은 사람들 중 제거할 사람을 고르기 위해 적절히 i += 3 해줘야 한다.
   👉🏻 제거된 사람, 즉 값이 0인 애들은 카운트를 건너 뛴다.
   👉🏻 역시 마찬가지로 i가 N을 넘냐 안넘냐에 따라 인덱스 표현이 달라진다.
   

항상 인덱스에 -1 해줘야 되는 점 때문에 더 까다롭게 느껴진 것 같다.

근데 성공하고 나서 보니까 다들 원래 큐를 써서 쉽게 푸는 건가 보다..
그 풀이는 스터디 모임 때 공부해보기로 하고 일단 넘기기로,,,~

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

int main() {
	//freopen("input.txt", "rt", stdin);
	int N, K;
	cin >> N >> K;
	vector<int> v;
	for (int i = 1; i <= N; i++) {
		v.push_back(i);
	}
	
	int i = K;
	int n = N;
	cout << "<";
	while(n--) {
		if (i <= N) {
			cout << v[i - 1];
			if (n) cout << ", ";
			v[i - 1] = 0;
		}
		else {
			cout << v[i - N - 1];
			if (n) cout << ", ";
			v[i - 1 - N] = 0;
			i = i - N;
		}

		int cnt = 0;
		while (cnt != K && n != 0) {
			if (i < N) {
				if (v[i] == 0) {}
				else cnt++;
				i++;
			}
			else {
				if (v[i - N] == 0) {}
				else cnt++;
				i = i - N + 1;
			}
		}
	}
	cout << ">";

	return 0;
}