#2146 c++ 백준 알고리즘 간단한 설명 및 코드

2164번: 카드2 (acmicpc.net)

2164번: 카드2

 

항상 문제를 풀때 가장 먼저 파악해야하는건 입력과 출력이다.

그런 후 제약조건을 확인하고 그것을 간소화하면 코드짜기 더욱 편하다.

 

규칙을 간소화하면 이렇다.

1. 1번은 제일 위 / N번은 제일 밑

2. 순환순서 :: i번째는 버리고 i+1번째는 맨 밑으로 이동

즉) N = 4일경우 1234 -> 1버리고 234 -> 342 -> 3버리고 42 -> 24 -> 2버리고 4

 

주로 STL로 풀이 가능한 문제들 stack queue vector등 모든 문제는 가끔 올리고 거의 안올리는 이유가

STL 사용자체로도 난이도가 매우 내려가기 때문..

 

아무튼

 

코드는 간단하다.

일단 N이 몇이던간  1부터 N까지 값이 나열되어 있어야하니 queue를 만들어서 for문으로 차례대로 넣어주고

큐에 단 하나의 값이 남을때까지 또 반복하면서 삭제 혹은 맨 뒤로 이동하면 되는데

 

STL queue는 인덱스 번지수로 접근하는게 아니므로 값을 뽑아 임시로 저장을 하고 pop을 한 후 맨 뒤에 push를 해주면 된다.

 

코드는 아래와 같다.

 

#include<iostream>
#include<queue>

using namespace std;

int main()
{
	// 규칙 간소화
	// 1. 1번은 제일 위 N번은 제일 밑
	// 순환순서 :: 첫번째는 버리고 두번째는 맨 밑으로   ex) N = 4 -> 1234 -> 1/버리고 234 -> 342  -> 3/버리고 24 -> 2/버리고 4
	int nInput{};
	queue<int> qData;
	cin >> nInput;
	for (int i = 1; i <= nInput; i++)
	{
		qData.push(i);
	}

	int i = 0;

	while(qData.size() != 1)
	{
		int nTemp{};
		if(i == 0 || i % 2 == 0)
			qData.pop();
		else if (i % 1 == 0)
		{
			nTemp = qData.front();
			qData.pop();
			qData.push(nTemp);
		}
		i++;
	}

	cout << qData.front() << endl;
}