====== 지우개 ======

===== 풀이 =====
  * N 제한이 매우 작아서 그대로 시뮬레이션을 돌려봐도 된다. 매 루프에서 길이 N/2, N/4, N/8, ..짜리 리스트들을 새로 만드는 식으로 구현한다면 총 시간 복잡도는 O(N)
  * 하지만, 더 쉬운 방법이 있다. 동작 방식을 보면, 2k+1 꼴의 숫자들을 지우고, 4k+2 꼴의 숫자들을 지우고, 8k+4꼴의 숫자들을 지우고,.. 하는 식이다. 이것은 다시 말하면 2의 배수만 남기고 지우고, 다음엔 4의 배수만 남기고 지우고, 8의 배수만 남기고 지우고.. 하는 것과 같다. 이렇게 해서 2^i의 배수가 한개만 남으면 그 수를 출력하는 것이므로, 바꿔 말하면 n이하에서 가장 큰 2의 거듭제곱수를 찾아서 출력하면 된다. 이것은O(1)에 계산 가능.

===== 코드 =====

==== 코드 1 - O(n) ====
<dkpr py>
"""Solution code for "BOJ 21756. 지우개".

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


def main():
    N = int(input())

    l = list(range(1, N + 1))
    while len(l) > 1:
        l = l[1::2]
    print(l[0])


if __name__ == '__main__':
    main()
</dkpr>


==== 코드 2 - O(1) ====
<dkpr py>
"""Solution code for "BOJ 21756. 지우개".

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


def main():
    N = int(input())
    print(1 << (N.bit_length() - 1))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:브론즈_2}}