BOJ 11866. 요세푸스 문제 0 (Python)

BOJ 11866. 요세푸스 문제 0

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

11866번: 요세푸스 문제 0

풀이

먼저 위의 그림처럼 그려보면서 문제를 이해하면 빠르다.
문제의 핵심은 원인 점과, 계속 3번째 사람을 구해야 하는데, 제거된 사람이 있는 자리는 건너 뛰어야 한다는 것이다.

나는 리스트를 이용해서, 제거된 사람을 -1로 표시하여 건너 뛰도록 하는 방법으로 구했다.

for _ in range(N):
    cur %= N
    next = 0

1. cur은 현재 위치이다. for 루프를 돌 때 마다 cur %= N을 해주어 cur이 항상 N보다 작게 해주어 인덱스를 벗어나지 않게끔 한다.

2. next = 0으로 설정하고 while문을 시작한다.

   if next == K - 1 and li[(cur + next) % N] != -1:
           result.append(li[(cur + next) % N])
           li[(cur + next) % N] = -1
           cur += K
           break

   1. next = K - 1이면서, li[(cur + next) % N]의 값이 -1이 아니면, 즉 제거된 사람이 아니면 결과에 append하고 제거한다(-1로 표시함)
      이때 항상 N으로 나누어 주어 out of range하지 않도록 주의한다.
      cur += K 해주어 현재 위치를 갱신한다.

   if li[(cur + next) % N] == -1:
           cur += 1
           continue

   2. 제거 된 인덱스일 경우엔 cur += 1 하고 아무것도 하지 않고 건너 뛴다

   next += 1

   3. 위의 경우에 하나도 해당하지 않을 경우엔 next를 증가시킨다.

3. 그렇게 다시 N번 루프를 돌면 된다.

 

위의 그림의 상황은 3,6,2,7이 제거된 상황이다.
1이 cur이였을때, 현재 -1도 아니고 next가 K-1도 아니므로 next를 증가하고
다음은 두번 다 제거된 인덱스이므로 cur을 두번 증가시킨다.
그렇게 되면 cur+next가 4를 가리키고 4는 -1도 아니므로 next를 1 증가시켜 next가 2가되고 5를 결과에 추가한다.

 

전체 소스코드

풀이

N, K = map(int, input().split())

li = [i for i in range(1, N + 1)]
result = []
cur = 0

for _ in range(N):
    cur %= N
    next = 0

    while True:
        # next가 K가 되면 제거
        if next == K - 1 and li[(cur + next) % N] != -1:
            result.append(li[(cur + next) % N])
            li[(cur + next) % N] = -1
            cur += K
            break
        # 제거 된 인덱스일 경우
        if li[(cur + next) % N] == -1:
            cur += 1
            continue
        # 아무것도 해당하지 않을경우 next증가
        next += 1

print("<", end="")
for i, n in enumerate(result):
    if i == len(result) - 1:
        print(n, end="")
    else:
        print(n, end=", ")
print(">")