2117 : 원형 댄스

• 백준 url

• 실버 1

시간제한	메모리제한	정답비율
2초	128MB	63.918%

in and out

• input : n

• output : 최소 자리바꿈 횟수

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)와 같은 경우도 순서는 반대가 되는 게 맞다.

가급적이면 자리를 최소로 바꾸려고 한다. 최소로 자리를 바꾸려면 어떻게 해야 할까?

# input setting
problem_num = 2117
import os, sys
path = os.getcwd() + f'\\txt\\{problem_num}'  + '.txt'
sys.stdin = open(path,'r')

n = int(sys.stdin.readline())

def circle_dance(n): #n 1~dd
    if n == 1 or n == 2:
        return 0
    elif n == 3:
        return 1
    else:
        a = int(n/2)
        b = n - int(n/2)
        a_ = [x+1 for x in range(a-1)]
        b_ = [x+1 for x in range(b-1)]
        c = sum(a_) + sum(b_)
        return c

result = circle_dance(n)
print(result)

6

• 참고

실제로 예시들을 구해보고 그 안에서 더 잘게 자를 수 있는 덩어리를 생각할 수 있어야할 것 으로 보인다. 결국 이 참고도 문제안의 문제를 점화식으로 나타내서 편하게 풀 수 있게 된 것.