취미로 코딩하기

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

이번에 볼 문제는 백준 1021번 문제인 회전하는 큐이다.
문제는 아래 링크를 확인하자.

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

2번 연산과 3번 연산은 단순히 서로 반대방향으로 큐를 회전시킨다.

한편, 연산을 최소 횟수로 쓰려면 수를 하나 뽑고 다음 수를 뽑을 때까지 한가지 연산만을 한다는 점을 생각하자.

따라서, 문제를 해결하기 위해 2번 연산을 사용하여 목표한 숫자를 뽑을 수 있을 때까지 큐를 회전시키는 횟수 cnt를 구하고, 반대로 회전시킬 때 필요한 횟수를 cnt를 이용하여 계산한 다음 둘 중 작은 값을 누적하면 답을 구할 수 있다.

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

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

queue<int> que;

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

	int N, M; cin >> N >> M;

	for (int i = 1; i <= N; i++) que.push(i);

	int ans = 0;
	while (M--) {
		int x; cin >> x;
		int cnt = 0;
		while (x != que.front()) {
			cnt++;
			que.push(que.front());
			que.pop();
		}
		ans += min(cnt, (int)que.size() - cnt);
		que.pop();
	}

	cout << ans;
}