[Python] BOJ 2164: 카드2

문제

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

접근 방법

처음에는 pop과 append만으로 쉽게 구현할 수 있을 것 같았으나, 시간 초과로 다른 방법을 찾다가 창의적인 접근 방법을 찾았다. 카드2 문제는 일종의 수학적 규칙이 존재했다. N개의 카드 갯수에 따라 맨 마지막에 남는 카드가 예상 가능하다.여기서 square(지수)는 N의 크기보다 커질때까지 2를 계속 곱해주기 때문에 유동적이다. 예제에 해당하는 공식은 다음과 같다. 출처 : https://tooo1.tistory.com/88

규칙을 발견하는 등 창의적으로 문제를 바라볼 수 있도록 공부를 많이 해야겠다는 생각이 들었다.

풀이

"""시간초과"""
# import sys

# N = int(sys.stdin.readline())

# deque = [i for i in range(1, N+1)]
# while len(deque) != 1:
#     deque.pop(0)
#     deque.append(deque[0])
#     deque.pop(0)

# print(deque[0])

"""수학적 접근 방법(성공)"""
import sys
N = int(sys.stdin.readline())
square = 2

while 1:
    if(N == 1 or N == 2):
        print(N)
        break

    square *= 2

    if(square >= N):
        print((N - (square//2))*2)
        break