[알고리즘][덱] 1021번 회전하는 큐 | baekjoon 문제 풀이

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

1021번: 회전하는 큐

 

 

연산의 최솟값을 출력하는 문제이다.

 

풀이

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

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int N, M, count = 0;
	cin >> N >> M;

	int arr[51];
	deque<int> dq;

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

	for (int i = 0; i < M; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (dq[j] == arr[i]) {
				int min_case = min(N - j, j); // 최소로 걸리는 거리를 계산
				if (min_case == j) { // 문제 2번 방법으로
					count += min_case;
					for (int k = 0; k < min_case; k++) {
						dq.push_back(dq.front());
						dq.pop_front();
					}
				}
				else { // 문제 3번 방법으로
					count += min_case;
					for (int k = 0; k < min_case; k++) {
						dq.push_front(dq.back());
						dq.pop_back();
					}
				}
				dq.pop_front();
				break;
			}
		}
		N--;
	}
	cout << count;
}

 

 

처음에는 최솟값을 구하는 문제이다 보니까 경우의 수가 많다고 생각하고 어려워했는데,

거리를 구하는 것처럼 단순 연산을 통해 case를 구분하여 계산하면 된다.

 

for문이 많아서 시간이 오래 걸릴 것 같다고 예상했는데, N의 범위가 작아서인지 괜찮았다.