[C++] BaekJoon 2164 카드2

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

---

 

처음 문제를 보고 큐를 이용해서 풀면 되겠다고 생각했다.

큐 헤더 파일을 이용하면 쉽게 풀 수 있는 문제지만 이를 사용하지 않고 문제를 풀어보고 싶었다.

 

코드

#include <iostream>
#define MAX 500000
using namespace std;

int main()
{
	int N,last;
	int first = 0;
	int arr[MAX]{};
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		arr[i] = i+1;
	}
	last = N - 1;

	while(1)
	{
		first += 1;
		if (first == last)
		{
			break;
		}
		last += 1;
		arr[last] = arr[first];
		first += 1;
		if (first == last)
		{
			break;
		}

	}
	cout << arr[last] << endl;
}

 

설명

N을 4라고 하자.

1번 카드가 제일 위 4번 카드가 제일 아래인 상태로 순서대로 카드가 놓인다.

이때 다음과 같은 동작을 카드가 하나 남을 때 까지 반복한다.

카드는 제일 위에서 1, 2, 3, 4 순서로 놓인다.
1을 버리면 2, 3, 4가 남고

2를 제일 아래로 옮기면 3, 4, 2

3을 버리면 4, 2가 되고

4를 밑으로 옮기면 2, 4가 된다.

마지막으로 2를 버리면 남는 카드는 4 

while(1)
{
	first += 1;
	if (first == last)
	{
		break;
	}
	last += 1;
	arr[last] = arr[first];
	first += 1;
	if (first == last)
	{
		break;
	}

반복문에서 first에 1을 더한다.

이는 arr[0]을 더 이상 계산에 포함하지 않음을 의미한다.

 

이후 first 값과 last 값이 동일할 때 반복문을 종료한다.

last 값에 1을 더하고 마지막 배열에 첫번째 배열의 값을 입력받는다.

첫 번째 숫자를 마지막으로 옮기는 과정이다.

 

이후 first 값에 1을 더한 후 값을 비교한다.

 

실행 결과