1278번: 연극

https://www.acmicpc.net/problem/1278


$O(2^n)$

2^n-1개의 장면이 가능하다.
즉, n자리 이진수를 한 비트씩 바꿔서 모두 표현하는 방법을 생각하면 된다.
실험적으로 작은 케이스를 손수 해결해서 규칙을 찾아보자.

i) n=1
1 1

ii) n=2
1 2 1 2

iii) n=3
1 2 1 3 1 2 1 3

iv) n=4
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 4

규칙은 꽤나 명확하게 보인다.

#include<cstdio>
int n;
void f(int x) {
    if (!x) return;
    f(x - 1);
    printf("%d\n", x);
    f(x - 1);
}
int main() {
    scanf("%d", &n);
    printf("%d\n", (1 << n) - 1);
    f(n);
    printf("%d", n);
    return 0;
}