[실버 IV] 1158번. 요세푸스 문제

 문제 

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

1158번: 요세푸스 문제

 사용 언어 

Python3

 풀이 과정 

요세푸스 순열의 규칙을 생각해서 나름 쉽게 풀었다. 그런데 출력 형식을 간단하게 구현하는데 고민을 많이 했다.

처음에는 다음과 같이 구현했는데 76ms가 나왔고, 후에 다른 사람들의 답안을 참고하여 출력 형식만 바꿔줬더니 72ms가 되었다.

from sys import stdin

N, K = map(int, stdin.readline().split())

table = [x for x in range(1, N + 1)]
Josephus = []
idx = 0

while table:
    idx = (idx + K - 1) % len(table)
    Josephus.append(table.pop(idx))

Josephus = ', '.join(map(str, Josephus))
print(f'<{Josephus}>')

기분 좋은 맞았습니다!!

 제출 답안 

from sys import stdin

N, K = map(int, stdin.readline().split())

table = [x for x in range(1, N + 1)]
Josephus = []
idx = 0

while table:
    idx = (idx + K - 1) % len(table)
    Josephus.append(table.pop(idx))

print('<' + str(Josephus).strip("[]") + '>')

 공부한 내용 

요세푸스 순열

따로 공부한 내용은 없지만 요세푸스 순열에 대해 찾아보았다. 요세푸스가 실제로 겪은 일을 바탕으로 만들어진 문제이고 요세푸스는 이 방법으로 마지막까지 살아남았다고 한다... 수학을 잘해서 살아남다니 똑똑한 사람들은 다르긴 다르네

 

문제는 다음 심화 문제를 위해서 점근식을 사용해야 하는데 내가 사용한 방법으로는 그 문제를 풀 수 없었다. 따라서 더 연구가 필요할 것 같다.

 

출처: https://namu.wiki/w/%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4%20%EB%AC%B8%EC%A0%9C