[백준/BOJ] 2164번 카드2 (C/C++)

백준 온라인 저지(BOJ) 2164번 카드2

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

2164번: 카드2

* 사용언어 : C언어, C++

 

1. 문제

1부터 N까지 번호의 카드가 위에서 아래로 순서대로 놓여있음

제일 위 카드를 버리고, 그 다음 제일 위 카드를 제일 아래로 옮기는 동작을 반복했을 때

마지막으로 남은 한 장의 번호를 출력

 

2. 풀이

FIFO(First In First Out)인 큐를 구현하면 풀 수 있는 문제입니다.

 

개인적으로 Linked List로 값을 실제로 넣고 빼는 방식보다는

넉넉한 크기의 배열을 만들고 head와 tail을 배열의 index로 보고 증가시키는 방식을 선호합니다.

 

메모리 공간이 넉넉하게 주어진 문제라면 이 방식을 사용하는 것이

구동 시간 절약에 큰 도움이 되니 참고하시길 바랍니다.

(pop을 했을 때 특별한 조치 없이 head만 1 증가시키면 됨, push도 배열의 ++tail 자리에 넣어주면 됨)

 

 

다만 이 방식은 배열의 크기를 잘 선언하는 것이 중요합니다.

이 문제는 N이 최대 500,000이고 절반이 버려지고 절반은 다시 push되는 방식입니다.

 

따라서 필요한 배열의 최대 크기는 500,000 + 250,000 + 125,000 + 62,500 + ... 이므로

무한 등비수열 합 공식에 의해 500,000 / (1 - 1/2) = 1,000,000이 됩니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
18258_카드2
5016KB	4ms
*/
#include <cstdio>

const int LM = 1000000;
int q[LM], h, t = -1, N;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) q[++t] = i;

	while (h < t) {
		++h;
		q[++t] = q[h++];
	}
	printf("%d\n", q[t]);
	return 0;
}