[백준 BOJ] 11866번 요세푸스 문제 0 (C++/cpp)

문제 설명

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

11866번: 요세푸스 문제 0

 

접근 방법 - 큐를 이용한 연산 문제

백준의 11866번 문제는 큐를 이용하여 해결해야 하는 수학적 사고력 문제이다.

해당 문제는, n개의 숫자에 대해 a번째 숫자를 순차적으로 제거하면서, 요세푸스 순열을 만들어야 하는 문제이다.

(문제에 대한 자세한 설명은 위를 참고하길 바란다.)

필자는 이 문제를 해결할 때, 제거해야 할 숫자는 바로 출력하며 pop 연산을 취하게끔 하였다.

다만 아닌 경우에는 해당 숫자에 대해 다시 큐에 push 연산을 취한 뒤에 pop 연산을 취하게끔 하였다.

자세한 설명은 아래에서 추가적으로 다루고자 한다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

예시 출력대로 출력하는 순서까지 아래에 함께 기재해놓았으니 이에 어려움을 겪고 있다면 참고하길 바란다.

 

코드의 실행 순서

1) n과 a를 순차적으로 입력받는다.

 

2) int형 큐를 선언한다.

 

3) n에 대해서, 1부터 n까지 순차적으로 큐에 push한다.

 

4) 연산을 시작하기 전, 우선 "<"를 출력한다.

 

5) 제어 변수 i를 1로 초기화하고, 큐가 비게 될 때까지 반복문을 실행하며 아래의 연산을 수행한다.

- i가 a에 나누어 떨어진다는 것은 현재 큐의 위치상 a번째 숫자가 된다는 것을 뜻하며, 이는 즉시 제거가 필요하다는 것을 뜻하기도 한다.

만일 해당 경우의 front값과 back값이 같다는 것은 제거되는 마지막 수라는 뜻이므로, 이 값만 출력한 뒤 pop 연산을 취한다.

만일 front값과 back값이 다르다면 추후에 제거될 숫자가 더 있다는 뜻이므로, 이 값과 함께 ,(콤마)를 출력한 뒤 pop 연산을 취한다.

- i가 a에 나누어 떨어지지 않는다는 것은 지금 제거될 숫자가 아니라는 뜻이다. 따라서 이 경우에선, front값을 다시 큐에 push한 뒤에 pop 연산을 취한다.

- 반복문을 한번 수행할 때마다 i에 1을 추가한다.

 

6) 5)의 반복문이 모두 끝났다면, ">"를 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <queue>
using namespace std;

//백준 11866번 코드
int main() {
	int n, a;
	cin >> n >> a;

	queue<int> q;
	for (int i = 1; i < n + 1; i++) {
		q.push(i);
	}

	cout << "<";
	int i = 1;
	while (!q.empty()) {
		if (i % a == 0) {
			if (q.front() == q.back()) {
				cout << q.front();
			}
			else {
				cout << q.front() << ", ";
			}
			q.pop();
		}
		else { q.push(q.front()); q.pop(); }
		i++;
	}
	cout << ">" << endl;
}

 

제출 결과

(2022.01.26 백준 11866번 문제 제출 결과)