[백준] 2164 카드2 Python

문제 링크

1. 문제 설명

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

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

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

2. 문제 접근

굉장히 노골적으로 큐 자료구조를 사용하라고 권장하는 문제입니다. 파이썬으로 치면 popleft()과 append()를 반복해 단 하나의 원소가 남을 때까지 반복하면 됩니다.

3. 문제 풀이

from collections import deque

def find_last_card(N):
    queue = deque(range(1, N+1))

    while len(queue) > 1:
        queue.popleft() 
        queue.append(queue.popleft())
    return queue[0]

N = int(input())
print(find_last_card(N))

4. 그런데..

이번 문제에서 카드를 제거하는 방식은 굉장히 규칙적입니다. 1, 3, 5 .. 한 칸씩 건너뛰며 끝 부분에 도달시 처음으로 돌아가 다시 카드를 제거하게 됩니다.
이와 비슷한 문제를 요세푸스 문제라고 합니다. 1부터 41까지 숫자를 원형으로 배치한 뒤 2부터 시작하여 건너뛰며 숫자를 제거합니다. 이 과정을 통해 마지막에 남는 숫자를 찾으려고 하는 거죠.

그런데 만약 전체 숫자의 개수가 $2^{n}$이라면, 바퀴의 첫 번째 숫자인 1은 마지막까지 제거되지 않습니다.

• 1. 첫 바퀴를 돌며 2, 4, 8, .. , $2^{n}$을 제거합니다. 제거되지 않은 숫자의 수는 $2^{n-1}$입니다.
• 2. 남은 수는 $2^{n-1}$개의 홀수들입니다. 1, 3, 5, 7 .. $2^{n}-1$ 등이 됩니다. 이 숫자를 앞뒤로 두 개씩 묶어 뒷부분 숫자들을 제거합니다. 그러면 $2^{n-2}$개 숫자들이 남고, 1은 계속 남습니다.
• 3. 이와 같이 귀납적 방법으로 1이 마지막까지 제거되지 않음을 증명할 수 있습니다.

따라서 바퀴 내에 $2^{n}$ 꼴의 숫자가 남아 있다면 마지막까지 제거되지 않는 수를 찾을 수 있습니다. $2^{n} + K (K<2^{n})$개의 수가 있다면 $K$개 만큼의 수 $2, 4, .. ,2*K$를 제거하면 바퀴 내에 $2^{n}$개의 숫자가 남으므로 $2*K+1$수가 마지막까지 제거되지 않음을 알 수 있습니다.
증명 링크

이 문제도 이와 같이 풀 수 있습니다. log함수를 통해 n값을 찾으면 $2^{n}$의 값도 알 수 있으며, 바퀴 내 전체 숫자 수를 알면 K값을 유도할 수 있습니다. 다만 문제에서는 1을 건너뛰지 않고 1부터 제거하므로 유의합시다.

import math

def find_last_card(N):
    M = 2 ** math.floor(math.log2(N))
    last_card = 2 * (N - M)
    return last_card if last_card != 0 else N

N=int(input())
print(find_last_card(N))