[백준] 회전하는 큐

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

1021번: 회전하는 큐

 

N이 50 이하의 자연수라 부담 없이 deque를 이용하여 풀었다.

2번을 이용하든 3번을 이용하든 숫자의 순서가 변하지는 않는다. 그러므로 P의 각 숫자를 뽑을 때 최솟값을 다 더해주면 된다.

2번 연산을 기준으로 숫자를 뽑았을 때 연산의 횟수를 x 라고 한다면 3번 연산의 방법을 이용한 연산의 횟수는 N-x 가 된다.

 

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
P = list(map(int, sys.stdin.readline().split()))
A = deque([i+1 for i in range(N)])
answer = 0

for i in P:
    a = A.popleft()
    cnt = 0
    
    while i != a:
        A.append(a)
        cnt += 1
        a = A.popleft()
    
    answer += min(N-cnt, cnt)
    N -= 1

print(answer)