C++[백준]12873번 기념품

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

12873번: 기념품

 

솔루션

---

나는 deque를 이용해 접근을하였다.

 

1) 먼저 dequ에 1~N 까지 넣어준다. (push_back())

2) t=1 턴 부터 시작해서 N-1턴 까지 반복하면서 아래의 과정을 반복한다.

 2-1) t^3을 구한다.

 2-2) 해당 값을 (N명 - t턴) 값으로 나눠준다.

 2-3) 나머지 만큼 dq.push_back(dq.front()), dq.pop_front() 를 해준다.

 

3) dq에 남은 마지막 한개를 출력한다.

 

 

코드

---

#define ll long long int
#include <iostream>
#include <cmath>
#include <deque>
using namespace std;

int N;
deque<int> dq;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

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

	for (int i = 1; i <= N - 1; i++) {
		ll p = pow(i, 3);
		p--;
		p %= (N - i + 1);

		while (p--) {
			dq.push_back(dq.front());
			dq.pop_front();
		}
		dq.pop_front();
	}
	cout << dq.front() << "\n";
}