[알골90제] 72번 - 공주구하기 (큐)

 

 

입력

- 왕자의 수 n

- 특정숫자 k

 

출력

- 최후의 남은 왕자

 

풀이

- 

- 원탁을 Q로 생각한다.

 

// 72번 - 공주구하기 : 큐 자료구조로 해결

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main() {

	int n, k;
	queue<int> Q;

	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) {
		Q.push(i);
	}

	//Q가 비어있을때까지
	while (!Q.empty()) {
		for (int i = 1;i < k; i++) { //k전까지 돌기
			Q.push(Q.front());
			Q.pop();
		}
		Q.pop();
		if (Q.size() == 1) { //1명 남았을 때
			printf("%d\n", Q.front());
			Q.pop();
		}
	}
	return 0;
}

- Q를 만들어 주고 queue<int> Q

- for문을 통해서 1부터 n까지의 수를 차례대로 큐에 넣어준다. 

for(int i = 1; i <=n; i++) Q.push(i);

- Q가 비어있을 때까지 while문을 진행한다. 

while(!Q.empty()) {}

- k때는 pop을 해줘야 하니깐 맨 앞에 있는 Q.font()를 맨 뒤로 집어 넣고, 맨 앞에것을 삭제하는 과정을 해준다

for(int i = 1; i<k; i++) {

   Q.push(Q.front()); //Q의 맨뒤로

   Q.pop; //Q의 맨앞 삭제

}

Q.pop; //k번째는 삭제

- 그리고 만약 큐에 1개의 자료만 남아을 경우 그 자료를 출력해준다. 최후의 왕자

if(Q.size() == 1) {

   printf("%d", Q.front());

   Q.pop(); //마지막 자료까지 pop해주면 Q가 empty == true 되기 때문에 while문이 종료 된다.

}

- 프로그램이 종료된다.