백준 20189 사탕 돌리기

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

20189번: 사탕 돌리기

제자리가 아닌 사탕이 있으면, 결국 그 사탕을 원래 자리로 옮겨줘야 하고, 그 과정을 잘 나누고 이어서 진행하면 문제가 해결될 것이라고 생각해 볼 수 있다. 특히 사탕을 옮겨 놓게 되면 그 위치는 사탕의 개수가 K+1개이므로, 제자리가 아닌 사탕이 있어 항상 그 자리에서 유의미한 이동을 이어 나갈 수 있음을 확인할 수 있다. 제자리에 가져다 놓은 사탕은 더 이상 이동할 일이 없다는 것이다. 

한 바퀴가 돌면, 제자리가 현재 위치보다 앞쪽인 사탕의 개수가 하나 줄어들게 되고, 유의미한 이동이 보장되어 바퀴의 수와 그 사탕의 개수가 같음이 보장되므로 그 개수만 세 주면 문제가 해결된다. 

하지만 1번 자리는 위의 공식이 적용될 수 없어 무의미한 이동이 발생할 가능성이 있으며, 처음 주어진 상태에 1번 자리가 완성돼 있으면 이를 해소하기 위해 1을 옮기고 다시 가져오는 한번의 이동이 추가로 필요하다. 이를 체크해 주면 문제를 해결할 수 있다.