백준 2164 카드2 큐가 아닌 벡터로 구현

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

2164번: 카드2

[문제 해석]

문제의 규칙은 단순합니다.

N 정수가 입력되었을 때, 1부터 N까지의 수들을 가지고 규칙을 적용하면 됩니다.

규칙은 1 숫자부터 시작하여 첫번째 수를 버리고, 두번째 수를 맨 뒤로 넣는 것을 반복하는 것입니다.

 

1. N = 6 일 때, 1 2 3 4 5 6 의 숫자들에 규칙을 적용해 1을 버리고 2를 맨뒤로 넣으면 3 4 5 6 2 가 됩니다.

2. 3 4 5 6 2 에 다시 규칙을 적용해 3을 버리고 4를 맨뒤로 넣으면 5 6 2 4 가 됩니다.

3. 5 6 2 4 에 다시 규칙을 적용해 5를 버리고 6을 맨뒤로 넣으면 2 4 6 이 됩니다.

4. 2 4 6 에 다시 규칙을 적용해 2를 버리고 4를 맨뒤로 넣으면 6 4 가 됩니다.

5. 마지막으로 6 4 에 규칙을 적용하면 6을 버리고 4가 남게되고 4가 정답입니다.

 

이제 코드 구현을 설명드리겠습니다.

main 문의 큰 틀부터 설명드리자면, N 변수를 할당하고 입력해줍니다.

이후 N_sup 벡터를 만들어 N 부터 1까지 역순으로 숫자를 넣어줍니다. ( 인덱스는 N N-1 ... 2 1 이렇게 구성되겠죠)

if 문을 보기에 앞서 else 문을 먼저 살펴보면, 결과값을 넣어줄 res 변수를 만듭니다.

res 변수에 넣을 값은 Card2 라는 함수의 리턴값이 될 것입니다. 

Card2 함수

Card2 함수를 자세히 살펴보면, Card2 함수에는 먼저 벡터 arr를 입력받고 새로운 벡터 arr2를 만들어줍니다. (Count 변수는 나중에 설명드릴게요)

본격적으로 규칙을 적용하기 위해 while 문을 활용하였고, if문을 통해 입력받은 arr의 길이를 arr.size()로 구할 수 있습니다.

입력받은 arr의 길이가 1보다 크다면, 규칙을 적용합니다.

Count 변수가 없다고 가정하고 if문속을 살펴보면 pop_back, push_back, pop_back 세 함수가 반복되는 구조임을 확인할 수 있습니다.

 

1. 규칙에서 첫번째 카드를 버리는 걸 pop_back으로 나타낸것이며, arr에는 초기에 역순으로 숫자들을 넣었기 때문에 1이 가장 나중에 들어온 숫자가 되고 pop_back함수는 가장 나중에 들어온 값과 그 값의 공간을 없애주는 함수라고 생각하시면 됩니다.
2. 그럼 1 숫자가 없어졌고, 이후 새로운 벡터 arr2에 arr의 마지막 인덱스 값인 2를 넣어줍니다. (마지막 인덱스 값을 구하기 위해서는 벡터이름[벡터이름.size()-1] 하시면 됩니다, 또한 push_back함수는 벡터에 원하는 값과 공간을 할당해주는 함수입니다.)
3. 그리고 마지막 인덱스인 2마저 pop_back을 하는 방식으로 이루어져 있습니다.

원래는 하나의 벡터에서 이루어지는 규칙을 다른시각에서 본것과 같습니다. 두 개의 벡터를 이용해서 결국 맨뒤로 보내질 숫자들을 새로운 벡터인 arr2에 저장되게 됩니다.

arr 벡터의 크기가 1보다 클때는 while문을 통해 계속해서 반복하게 되고, N = 6 인 예제를 예시로 든다면 arr2 에는 현재 2 4 6 세개의 원소가 들어있는 겁니다.

이제 arr 벡터의 크기가 1보다 작거나 같아진다면 else if 혹은 else 문으로 가게됩니다.

Count 변수는 나중에 살펴볼 예정이니 else if문과 else문을 같다고 보시면, if 문에 arr2 벡터가 크기가 1인 경우이면 즉, 현재는 2 4 6 세원소가 있겠지만 계속 규칙을 반복해 결국 4만 남았다면 4를 리턴해주시면 된다는 의미입니다.

하지만 현재는 2 4 6 으로 세원소가 있으므로 else문으로 넘어가고, 이때 arr2 벡터는 뒤집어준 후 Card2 함수를 반복해줍니다.

구체적으로 설명드리자면,

 

1.  stl의 reverse 함수는 벡터의 원소들을 뒤집어주는 함수라고 보시면됩니다. 현재 arr2에는 2 4 6 원소가 들어가있으므로 6이 가장 마지막에 들어온 원소입니다.
   1. 이때 pop_back이라는 함수를 사용한다면 6이라는 숫자가 버려질 것입니다.
   2. 하지만 처음 맨뒤로 보내진 2가 현재 맨위로 올라와 pop_back을 할때, 2가 버려져야 하기때문에 arr2를 뒤집어주어 6 4 2 가되도록 해줍니다.
   3. 이제 pop_back 함수를 적용하면 2가 버려지고 최종적으로 4가 남겠군요! (6도 버려질테니)
2. 그 다음으로 리턴값에서 Card2 함수를 또 사용합니다?! 이런걸 보통 재귀함수라고 합니다.
   1. 하지만 이번에는 arr 벡터를 가지고 하지 않고 arr2 벡터를 가지고 Card2 함수를 다시 반복하게 됩니다.
   2. 그렇다면 처음에는 arr 벡터로 6 5 4 3 2 1 이 들어갔지만 규칙이 적용된 arr2 6 4 2 가 arr로 들어가 또다시 규칙이 적용이 되는 방식입니다.
   3. 이렇게 재귀함수를 반복하며 결국 arr2벡터의 크기가 1이 되는 시점에서 우리는 arr2[0] 값을 리턴해준다면 그것이 정답인겁니다!
3. 하지만 제가 설명드리지 않은 Count라는 변수가 존재하네요.

반례

Count 변수를 굳이 하나 만들어준 이유는 백준에서 악명으로 유명하다는 반례에 대한 대처입니다.

대충 16이라는 값을 넣으면 코드는 잘 돌아갈 것입니다. 그 이유는 1~16 숫자에 규칙을 적용하면 첫번째 규칙이 적용된 이후 숫자 개수는 8개, 두번째 규칙 이후 숫자 개수는 4개, 세번째 2개, 1개로 정답이 나올때까지 짝수개의 숫자를 유지합니다.

하지만 만약 20이라는 숫자를 넣었다고 생각해봅시다.

첫번째 규칙 이후 10개의 숫자가 남을것이고, 두번째 규칙 이후 5개의 숫자가 남아 홀수가 될 것입니다.

하지만 홀수인경우 Card2 함수의 while문 시작부분의 첫 if문에서 pop_back함수를 2개 사용한다면 결과가 달라지게 됩니다.

예시로 설명드리자면, N = 20 일 때,

1. 첫 규칙 이후 숫자들은 2 4 6 8 10 12 14 16 18 20 으로 10개일겁니다.
2. 두번째 규칙 이후 숫자들은 4 8 12 16 20 으로 5개일겁니다.
3. 새번째 규칙에서 문제가 발생하는데, 8 16 이라는 숫자만 남으며 뒤의 20의 숫자가 버려지게됩니다.
4. 이 경우에 원래의 Card2함수라면 네번째 규칙에서 8숫자를 버리고 16을 정답으로 선택하게됩니다.
5. 하지만, 규칙을 알고있는 우리들은 이미 20이 버려졌기때문에 8이 뒤로가고 16이 다시 버려져, 8이 정답이라는걸 알고있습니다.

그렇기 때문에 우리는 여기서 홀수이거나 짝수개의 숫자가 있을 때, 규칙을 다르게 적용해야한다는걸 알 수 있습니다.

짝수인경우 arr2벡터가 들어오면 원래대로 pop_back 두 번을 통해 숫자 두 개를 버려주면 되지만,

홀수인경우 arr2벡터가 들어오면 이미 숫자가 한번 버려졌으니 처음에는 pop_back을 한번 적용해주어야 합니다.

이를 위해서 저는 Count 변수를 만들었습니다.

처음 Card2 함수를 실행할때는 Count = 0 을 넣어 원래대로 코드가 작동하게 합니다.

하지만 arr.size() == 1 인 경우, 즉 N=20의 2. 에서 20이라는 숫자가 남은경우 Count = 1 으로 값을 바꿉니다.

이러면 다음 Card2 함수가 실행될 때 Count = 1 을 넣어주기 때문에 pop_back함수가 한번 발동하지 않게됩니다. (if(Count!=1) 이라면 Count가 1이 아닐때 pop_back 함수가 실행되므로 처음의 pop_back함수는 실행되지 않게됩니다.

 

이런식으로 벡터와 사고력만을 가지고 우리는 문제를 풀 수 있게됩니다. (물론 stl 함수라는 조미료가 조금 들어가긴했지만..)

요약

벡터의 pop_back, push_back 성질 및 stl 함수 size, reverse 함수들의 응용

1개의 벡터가 아닌 2개의 벡터를 사용하는 아나더 사고방식

규칙을 적용할 때 숫자들의 개수에 주의하여 대처  

[정답 코드]

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>

using namespace std;

int Card2(vector<int> arr, int Count)
{
	vector<int> arr2;

	while (1)
	{
		if (arr.size() > 1)
		{
			if (Count != 1)
			{
				arr.pop_back();

			}
			else
			{
				Count = 0;
			}
			arr2.push_back(arr[arr.size() - 1]);
			arr.pop_back();
		}
		else if (arr.size() == 1)
		{
			Count = 1;
			if (arr2.size() == 1)
			{
				return arr2[0];
			}
			else
			{
				reverse(arr2.begin(), arr2.end());
				return Card2(arr2, Count);
			}
		}
		else
		{
			if (arr2.size() == 1)
			{
				return arr2[0];
			}
			else
			{
				reverse(arr2.begin(), arr2.end());
				return Card2(arr2, Count);
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N; cin >> N;
	vector<int> N_sup;

	for (int i = 0; i < N; i++)
	{
		N_sup.push_back(N - i);
	}

	if (N_sup.size() == 1)
	{
		cout << N_sup[0];
		return 0;
	}
	else
	{
		int res;
		res = Card2(N_sup, 0);
		cout << res;
		return 0;
	}
}