카드 2
면접 대비시간 제한2초메모리 제한128 MB
카드를 버리고 다음 카드를 맨 아래로 옮기는 과정을 반복해 마지막에 남는 카드 번호를 구하는 문제입니다.
문제
N장의 카드가 한 줄로 쌓여 있다. 카드에는 위에서부터 차례대로 1부터 N까지 번호가 붙어 있으며, 처음에는 1번 카드가 맨 위, N번 카드가 맨 아래에 있다.
카드가 한 장만 남을 때까지 다음 두 동작을 반복한다.
- 맨 위의 카드를 버린다.
- 남은 카드가 있다면, 새 맨 위 카드를 맨 아래로 옮긴다.
N = 4라면 처음 순서는 1, 2, 3, 4이다. 1을 버린 뒤 2를 아래로 옮기면 3, 4, 2가 되고, 이어서 3을 버리고 4를 아래로 옮기면 2, 4가 된다. 마지막으로 2를 버리면 4만 남는다.
N이 주어졌을 때 마지막에 남는 카드 번호를 구하시오.
입력
첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 500,000)
출력
첫째 줄에 마지막에 남는 카드의 번호를 출력한다.