(Python) - BOJ(2164번) : 카드 2

 

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

2164번: 카드2

---

• 해설 : 

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 문제이다.

 

 

---

• 풀이 :

큐를 이용하여 순환시키는 방식으로 구현하면 된다. 요세푸스 순열과 비슷한 문제이다.

 

 

 

---

• 소스코드 : 

 

import sys
from collections import deque
input = sys.stdin.readline
 
if __name__ == "__main__":
    nums = deque([i for i in range(1,int(input())+1,1)])
    last = nums[0]
    while nums:
        last = nums[0]
        nums.popleft()
        if nums:
            last = nums[0]
            nums.append(nums.popleft())
    print(last)