시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 181 | 94 | 78 | 58.647% |
N(1 ≤ n ≤ 32767)명의 사람들이 잔치에서 춤을 추게 되었다. 처음에는 1번부터 N번까지의 사람들이 차례대로, 둥글게 손을 잡고 서 있다. 그리고 춤이 끝날 때에는 이 순서가 반대(거꾸로, 뒤집힌)가 되어야 한다. 물론 사람들이 모두 손을 놓고 다시 자리를 잡으면 되겠지만, 그렇게 하면 둥그런 모양이 깨지게 된다. 따라서 자리를 바꿀 때에는, 서로 손을 잡고 있는 두 명의 사람만 자리를 바꿀 수 있다.
예를 들어 n=6인 경우를 보자. 맨 처음의 순서는 (1, 2, 3, 4, 5, 6)이 된다. 둥글게 서 있기 때문에 1번과 6번도 손을 잡고 있다. 이제 (1, 2, 3, 4, 5, 6) → (6, 2, 3, 4, 5, 1) → (2, 6, 3, 4, 5, 1) → (1, 6, 3, 4, 5, 2) → (1, 6, 3, 5, 4, 2) → (1, 6, 5, 3, 4, 2) → (1, 6, 5, 4, 3, 2)의 순서대로 바꾸면 자리가 반대가 된다. (6, 5, 4, 3, 2, 1)이 되는 게 맞겠지만, 어차피 둥글게 서 있기 때문에 (1, 6, 5, 4, 3, 2)와 같은 경우도 순서는 반대가 되는 게 맞다.
가급적이면 자리를 최소로 바꾸려고 한다. 최소로 자리를 바꾸려면 어떻게 해야 할까?
첫째 줄에 n이 주어진다.
첫째 줄에 최소 자리바꿈 회수를 출력한다.
6
6
5
4
4
2