카드 마술
시간 제한2초메모리 제한128 MB
카드를 앞에서 뒤로 옮기고 내려놓는 과정을 반복했을 때 1부터 N까지 순서대로 놓이도록 초기 카드 배열을 구하는 문제입니다.
문제
1부터 N까지 번호가 적힌 카드 N장이 한 줄로 놓여 있다. 카드를 미리 어떤 순서로 놓아야 다음 마술을 할 때 책상에 내려놓는 카드가 차례대로 1, 2, ..., N이 되는지 구하려고 한다.
i번째 단계(1 <= i <= N)에서는 남아 있는 카드 더미에서 맨 앞 카드를 맨 뒤로 옮기는 일을 i번 반복한 뒤, 맨 앞 카드를 책상 위에 내려놓는다. 이때 내려놓는 카드는 i여야 한다.
N이 주어졌을 때, 이 조건을 만족하는 카드의 초기 순서를 출력하시오.
입력
첫째 줄에 카드의 개수 N이 주어진다.
- 1 <= N <= 1,000
출력
초기 카드 더미의 앞에서부터 뒤까지 번호를 한 줄에 공백으로 구분해 출력한다.
힌트
초기 순서가 2 1 4 3이면 다음과 같이 진행된다.
- 맨 앞의 2를 뒤로 옮겨 1 4 3 2가 되고, 1을 내려놓는다.
- 남은 더미 4 3 2에서 맨 앞 카드를 두 번 뒤로 옮겨 2 4 3이 되고, 2를 내려놓는다.
- 남은 더미 4 3에서 맨 앞 카드를 세 번 뒤로 옮겨 3 4가 되고, 3을 내려놓는다.
- 마지막으로 4를 내려놓는다.