2164: 카드2

-Class2 : Silver5

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

2164번: 카드2

 

-결과

 

-코드

#include <stdio.h>
#define size 500000
int main()
{
	int n, i, front=0, rear;
	int que[size];
	scanf("%d", &n);
	
	for(i=0; i<n; i++) que[i]=i+1;
	rear=n-1;
	
	while(1) {
		front=(front+1)%n;
		if(rear==front) break;
		rear=(rear+1)%n;
		que[rear]=que[front];
		front=(front+1)%n;
		if(rear==front) break;
	}
	printf("%d", que[rear]);
	return 0;
}

 

-풀이

카드의 개수를 입력받고 제일 위에 있는 카드를 버린 후 제일 위에 있는 카드를 맨 아래로 넣는 것을 계속 반복하는 문제이다.

이 문제는 큐를 이용해서 풀면 되는데 입력 사이즈가 500000개가 넘기 때문에 메모리를 아끼기 위해 원형큐를 사용해야 한다.

헤드포인터인 front 값을 1 증가시키고, rear값과 front값이 같다면 원형큐에 숫자가 1개 남아있다는 의미이므로 반복문을 벗어난다. rear에 1을 증가하고, que[rear]에 que[front]을 대입하고 front에 1을 증가한 후 rear값과 front값이 같다면 원형큐에 숫자가 1개 남아있다는 의미이므로 반복문을 벗어난다.