Baekjoon 1158 요세푸스 문제 파이썬

요즘 파이썬도 틈틈이 공부하고자 간단한 문제들은 파이썬을 이용해 해결해보고 있다.

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

1158번: 요세푸스 문제

https://github.com/JUNGSOONIL/PYTHON/blob/main/BAEKJOON%201158

GitHub - JUNGSOONIL/PYTHON: 파이썬 코드

 

1번부터 N 번까지 사람이 원을 이루고 앉아있고 K 번째 사람을 계속 제거해 나가면서 남은 사람끼리 계속 원을 이루어 모든 사람을 제거해나가는 과정을 (N, K)요세푸스라고 한다.

만 약 (7, 3)요세푸스의 경우 아래 그림과 같다.

처음엔 3 그다음엔 6 그다음엔 7,1을 지나 2 그리곤 7 그다음엔 5 ,1 ,4 순이다.

​

처음 문제를 해결할 땐 그냥 반복문을 이용해서 K씩 증가시키고 범위를 넘어서면 초기화하고 이런 식으로 해결하려고 하였으나 이미 사라진 데이터까지 포함해 버리는 것을 확인할 수 있었고 이에 카운트를 이용해 초기화되지 않은 위치를 지날 때마다 카운트하여 K와 같아지면 해당 데이터를 가져오는 식으로 문제를 해결하였다.

​

처음 파이썬으로 제출하였을 땐 시간 초과가 발생하였는데, 구글링 도중 아래 문구를 확인하여 pypy로 제출해 해결하였다.

​