사용자 도구

사이트 도구


ps:problems:boj:2164

카드2

ps
링크acmicpc.net/…
출처BOJ
문제 번호2164
문제명카드2
레벨실버 4
분류

요세푸스 문제

시간복잡도O(1)
사용한 언어Python
제출기록29200KB / 76ms
최고기록52ms
해결날짜2021/08/05

풀이

  • 카드1에서 N의 범위를 늘리고, 마지막 남는 카드만 출력하게 변형한 문제.
  • N이 늘어났지만, 그래도 최대 500,000 이기 때문에 deque를 사용해서 O(n)에 구현해도 여유있게 풀리기는 한다.
  • 그러나 이 문제에서 카드를 조작하는 것이 요세푸스 문제와 같은 패턴이고, 전체 시퀀스가 아니라 마지막에 남는 카드만 출력하면 되기 때문에, 요세푸스 문제에서 설명한 효율적인 방법을 적용할 수 있다.
    • 여기에서는 k=2이므로, 그냥 공식에 바로 대입해서 풀 수 있다.
      • $ J_{n,2} = 1+2(n-2^{\lfloor{log_{2}n}\rfloor}) $
      • 요세푸스 문제에서는 처음으로 제거하는 수가 2가 된다. 윗 공식의 J(n,2)도 그 경우에 마지막으로 남는 수를 찾는 공식이다. 이 문제에서는 요세푸스 문제와 달리 처음 제거하는 수가 1이다. 그래서 위의 공식에서 구한 J(n,2)에서 1을 뺀 값을 답으로 출력하면 된다. 만약 그 값이 0이 되는 경우에는 (N=2^x인 경우), N을 대신 답으로 출력해주면 된다.
      • 이렇게 하면 시간복잡도는 O(1)

코드

코드 1 - 공식을 사용

"""Solution code for "BOJ 2164. 카드2".

- Problem link: https://www.acmicpc.net/problem/2164
- Solution link: http://www.teferi.net/ps/problems/boj/2164
"""


def main():
    N = int(input())  
    answer = ~(1 << N.bit_length()) & (N << 1)
    if answer == 0:
        answer = N
    print(answer)


if __name__ == '__main__':
    main()

코드 2 - Deque로 시뮬레이션

"""Solution code for "BOJ 2164. 카드2".

- Problem link: https://www.acmicpc.net/problem/2164
- Solution link: http://www.teferi.net/ps/problems/boj/2164
"""

import collections


def main():
    N = int(input())
    deq = collections.deque(range(1, N + 1))
    while deq:
        discarded_card = deq.popleft()
        deq.rotate(-1)
    print(discarded_card)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
W G E M A
 
ps/problems/boj/2164.txt · 마지막으로 수정됨: 2021/08/06 09:37 저자 teferi