[BOJ 12721 // C++] Mousetrap (Small)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 12721번 문제인 Mousetrap (Small)이다.
문제는 아래 링크를 확인하자.

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

12721번: Mousetrap (Small)

12722번 문제에서 입력이 작아진 형태이다. 문제를 효율적으로 해결하고 싶다면 해당 글을 참고하여 문제를 해결하자.

 

위의 글과 같은 어려운 구현을 하지 않더라도 Small버전은 아래와 같이 deque을 이용해 직접 전체 과정을 거꾸로 시뮬레이션해나가는 것으로 해결할 수도 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <deque>
using namespace std;

int ans[5001];

void solve() {
	deque<int> dq;
	int K; cin >> K;
	dq.push_back(K);
	for (int i = K - 1; i > 0; i--) {
		dq.push_front(i);
		for (int j = 0; j < i - 1; j++) {
			dq.push_front(dq.back());
			dq.pop_back();
		}
	}

	for (int i = 1; i <= K; i++) {
		ans[i] = dq.front();
		dq.pop_front();
	}

	int Q; cin >> Q;
	while (Q--) {
		int x; cin >> x;
		cout << ans[x] << ' ';
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case #" << t << ": ";
		solve();
	}
}