1278번: 연극

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

 

영화의 장면마다 배우가 들어갔다 나갔다 하는데 배우의 조합이 겹치면 안되며, 한번에 1명씩만 이동 가능하다. 또한, 시작 전과 종료에는 장면에 배우가 없어야 하므로 첫 장면과 마지막 장면은 1명만 있어야 한다. 배우의 수가 주어질 때, 만들 수 있는 최대 장면의 수를 구하는 문제이다.

 

n명으로 만들 수 있는 최대 조합의 수는 2^n이며 공집합을 제외하면 2^n-1이 된다. 처음에는 최적화된 제귀 함수를 이용하면 풀릴 수 있을거라 생각했으나, n이 17까지 주어지므로 이는 불가능함을 깨닫게 되었다. 이에 모든 부분집합을 작은 변화로 방문할 수 있는 그레이 코드 원리를 이용하게 되었다. 그레이 코드는 이진수에서 비트 하나만 바꾸며 모든 수를 표현하는 원리이며, i번째 이동에서 바뀌는 배우의 번호는 i를 이진수로 나타냈을 때 가장 오른쪽에 있는 1의 위치가 된다. Integer.numberOfTrailingZeros()를 사용하여 가장 오른쪽 1을 찾았으며, 1부터 n까지기 때문에 +1을 해주었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class 연극1278 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int maxScenes = (1 << n) - 1;
        StringBuilder sb = new StringBuilder();
        sb.append(maxScenes).append("\n");
        
        for (int i = 1; i <= (1 << n); i++) {
            int actor = Integer.numberOfTrailingZeros(i) + 1;
            if (i == (1 << n)) {
                sb.append(n);
            } else {
                sb.append(actor).append("\n");
            }
        }
        
        System.out.print(sb);
    }
}