지우개

면접 대비

시간 제한1초메모리 제한512 MB

요약

1부터 N까지 차례로 놓인 수에서 홀수 번째 위치의 수를 지우고 왼쪽으로 당기는 과정을 하나가 남을 때까지 반복한 뒤 남는 수를 구한다.

문제

$N$ 개의 칸에 $1$ 부터 $N$ 까지의 수가 왼쪽부터 순서대로 저장되어 있다. 각 칸에도 왼쪽부터 $1$ 부터 $N$ 까지 번호가 순서대로 붙어 있다. 즉, 처음에는 각 칸의 번호와 그 칸에 저장된 수가 같다.

아래 그림은 $N = 7$ 일 때의 예이다.

수가 정확히 하나 남을 때까지 다음 작업을 반복한다.

(A) 홀수번 칸의 수를 모두 지운다. (B) 남은 수를 왼쪽으로 모은다.

첫 번째 작업의 (A) 단계가 끝나면 칸들의 상태는 다음과 같다.

(B) 단계가 끝나면 다음과 같다.

두 번째 작업이 진행되면 칸들은 아래 두 그림과 같이 바뀐다.

이제 수가 하나 남았으므로 작업은 더 이상 진행되지 않는다.

$N$ 을 입력으로 받아 위와 같이 작업을 진행했을 때 마지막으로 남는 수를 계산하는 프로그램을 작성하라.

첫 번째 줄에 정수 $N$ 이 주어진다.

마지막으로 남는 수를 한 줄에 출력한다.