PS 이야기

1214 A. 조약돌 순서 처음에 $[1, 2, 3, ..., K]$이 적혀있는 크기 $K$인 배열 $A$가 있다. $i = 1$부터 시작하여 $A_i$와 $A_{i+1}$의 값을 바꾼다. 그리고 $i$를 $1$ 증가시킨다. 만약 $i = K-1$이라면 다음 $i$의 값은 $K$가 아니라, $1$이 된다. 바꾸는 작업을 $N$ 번 하였을 때, 최종 배열의 상태를 구하는 문제다. 값을 바꾸는 횟수 $N$이 최대 $10^{18}$로 굉장히 크다. 바꾸는 작업을 $K \times (K-1)$ 번 하면 배열이 원래 상태로 돌아오고, 바꾸는 작업을 $K-1$ 번하면 맨 왼쪽에 있던 값이 맨 오른쪽으로 가는 것을 알 수 있다. 이 점을 이용하여, $O(K)$ 시간복잡도에 해결할 수 있다. 더보기 #include u..