[백준] 1278 - 연극 (c++)

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

 

문제 요약

무대가 있다. 한 장면이 끝날 때마다 무대에 있는 배우 한 명이 내려오거나 대기중인 배우 한 명이 무대로 올라갈 수 있다.

각 장면의 배우 구성을 모두 다르게 할 때, 최대 장면 수와 그에 맞는 배우들의 움직임을 출력해라.

 

풀이 (2^N)

• 재귀

배우가 올라와 있거나 내려와 있거나 둘중 하나 배우 N명이니까 2^N, 다 내려와있는 경우 -1 해서 장면 개수는 2^N-1이고 배우 움직임은 백트래킹 느낌으로 돌려주면 구할 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0),cout.tie(0);
    int n;cin>>n;

    cout<<(1<<n)-1<<'\n';
    function<void(int)> fn = [&](int i) -> void {
        if (i == 0) return;
        fn(i - 1);
        cout << i << '\n';
        fn(i - 1);
   };
   fn(n);
   cout<<n;
}