[백준][12873] 기념품

이 포스트는 백준 사이트의 기념품 문제 풀이입니다.

문제

해결 과정

이 문제는 STL 컨테이너 중 하나인 Deque을 활용하면 쉽게 해결할 수 있습니다.

문제에서는 백준이가 움직이지만, Deque을 활용한 풀이에서는 백준이가 아닌
N명의 사람이 차례마다 백준이 앞에 오는 것으로 Deque의 양방향 연산(Push, Pop)을 활용하였습니다.

또한 매번 \(t^3\) 번 순차탐색을 진행하면 시간이 부족하므로
N으로 나눈 나머지를 활용하여 최단 짧은 거리로 연산하도록 하였습니다.

코드 구현

#include <iostream>
#include <deque>
#include <cmath>

using namespace std;

int main() {
	int N;
	cin >> N;
	deque<int> dq;	
	for(int i = 1; i <= N; ++i) {
		dq.push_back(i);
	}

	for(int t = 1; t < N; ++t) {
		long long idx = pow(t, 3) - 1;
		idx %= (N - t + 1);

		while(idx--) {
			dq.push_back(dq.front());
			dq.pop_front();
		}

		dq.pop_front();
	}

	cout << dq.front();
	return 0;
}

실행 결과