백준 25559 - 패스 [Python]

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

25559번: 패스

---

풀이 과정

원형으로 앉아있는 사람들 N명끼리 1 ~ N이 써져 있는 카드를 뽑고 버린 후, 뽑은 숫자만큼 공을 오른쪽으로 패스해서, 모든 사람들이 1번씩 공을 패스받았을 때 공이 이동한 순서를 출력하는 문제이다.

 

N번 카드를 뽑는 것은 공을 맨 처음 가지고 있는 1번 사람만이 가능하다. 1번 사람을 제외한 모든 사람은 공을 받으려면 일단 타인에게 패스를 받아야 하는데, N번 카드를 뽑으면 공이 한 바퀴 돌아서 자신에게 돌아오기 때문에 패스를 2번 받게 되어버리기 때문이다.

 

첫 번째 사람을 N번 카드를 뽑는다고 고정시키면, 나머지 카드는 1 ~ N-1이 남게 된다. 그런데 N이 홀수라면, 남은 카드의 합 (N(N-1) / 2) - N이 N의 배수가 되어 첫 번째 사람이 패스를 최소 1번 추가로 받게 된다. 따라서 N이 1을 제외한 홀수인 경우 모든 사람이 한 번씩만 패스를 받을 수는 없다.

 

N이 짝수인 경우 N, 1, N-2, 3, N-4, 5, N-6, 7 ... 순으로 카드를 뽑아서 패스할 경우 모든 사람이 한 번씩만 패스를 받을 수 있다. 다른 경우도 더 존재할 것 같지만 저런 케이스를 출력하여 문제를 해결하였다.

---

소스 코드

import sys

N = int(sys.stdin.readline())
if N == 1:
    print(1)
    exit(0)
if N % 2 == 1:
    print(-1)
    exit(0)

answer = []
left = N
right = 1
while(True):
    answer.append(str(left))
    left -= 2
    if len(answer) == N:
        break
    answer.append(str(right))
    right += 2
    if len(answer) == N:
        break

print(' '.join(answer))