(BOJ) 1278 연극

1278 연극

• 분류 : 수학, 재귀

문제

연극극단 “월드”는 2009년 새해를 맞아 새로운 연극을 기획 중이다. 이 연극에는 새로운 오디션을 통해 선발된 N명의 신인 배우들만이 출연할 예정이다. 극단을 운영하고 있는 김형택 사장의 지시에 따라, 당신은 아래의 조건을 만족시키는 참신한 연극을 만들어야 한다.

연극은 연속된 K개의 장면으로 구성되게 된다. 그리고 각 장면에는 적어도 한 명 이상의 배우가 무대에 서 있어야 한다.

하나의 장면이 계속되는 동안에는 무대에 서는 배우들이 바뀔 수 없다. 즉 장면 중간에 새로운 배우가 무대로 나오거나, 무대에 있던 배우가 무대 뒤로 들어가는 일은 없다.

무대가 혼란스러워지는 것을 방지하기 위해, 한 장면이 끝나고 다음 장면으로 넘어갈 때에는 단 한 명의 배우만 이동해야 한다. 즉 새로운 배우 하나가 무대로 나오거나, 무대에 있던 배우 하나가 무대 뒤로 들어가는 경우만이 허용된다.

연극이 시작되기 전과, 연극이 끝나고 난 후에는 무대가 비어 있어야 한다. 따라서 첫 번째 장면과 마지막 장면에서는 무대 위에 한 명의 배우만이 있어야 한다.

각 장면에서 무대에 서는 배우들의 구성은 장면마다 달라야 한다. 예를 들어 한 장면에서 배우 2, 배우 3, 배우 5가 출연했다면, 동일한 세 명의 배우가 무대에 서는 장면이 있어서는 안 된다.

신인 배우들에게 보다 많은 기회를 주기 위해, 연극은 가능한 많은 장면으로 구성되어 있어야 한다. 즉 K를 최대로 해야 한다.

예를 들어 N=2인 경우, 아래와 같이 연극을 구성하면 모든 조건을 만족시키게 된다.

• 연극이 시작되기 전:
  • (배우 1) 무대로
• 첫 번째 장면: (배우 1)
  • (배우 2) 무대로
• 두 번째 장면: (배우 1), (배우 2)
  • (배우 1) 뒤로
• 세 번째 장면: (배우 2)
  • (배우 2) 뒤로
• 연극이 끝나고 난 후:

배우의 수가 주어지면, 극단의 매니저 김수현을 도와 연극을 구성하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (2 ≤ N ≤ 17) 신인 배우들은 1부터 N까지 순서대로 번호가 매겨진다.

출력

첫째 줄에 조건을 만족시키는 최대의 장면 수 K를 출력한다. 두 번째 줄에는 첫 번째 장면에 무대로 나올 배우의 번호를 출력한다. 세 번째 줄부터 K-1개 줄에 걸쳐 각 장면이 끝나고 다음 장면으로 넘어갈 때 무대로 나오거나 무대 뒤로 들어가는 배우의 번호를 출력한다. K+2번째 줄에는 마지막 장면에서 무대에 서게 되는 배우의 번호를 출력한다. 연극을 구성하는 방법이 둘 이상이면 아무 것이나 하나 출력한다.

예제 입력 1

2

예제 출력 1

3
1
2
1
2

Solution 1

Exapnder

import java.util.*
import kotlin.math.pow

private var N: Int = 0
private var input = mutableListOf<String>()


fun main() {
    input()
    solve()
}

private fun input() = with(Scanner(System.`in`)) {
    N = nextInt()
}

private fun solve() {
    val K = 2.calculateK(N)
    println(K)
    recursive(N)
    println(N)
}

private fun recursive(n : Int) {
    if (n == 0) return
    recursive(n - 1)
    println(n)
    recursive(n - 1)
}

fun Int.calculateK(n: Int): Int {
    return this.toDouble().pow(n).toInt() - 1
}

Solution 2

Exapnder

import java.util.*

private var N: Int = 0
private var input = mutableListOf<String>()


fun main() {
    input()
    solve()
}

private fun input() = with(Scanner(System.`in`)) {
    N = nextInt()
}

private fun solve() {
    val K = (1 shl N) - 1
    println(K)
    recursive(N)
    println(N)
}

private fun recursive(n : Int) {
    if (n == 0) return
    recursive(n - 1)
    println(n)
    recursive(n - 1)
}

Point of Thinking

• 문제의 조건을 잘 살펴보아야 한다.
• 배우들은 이미 인덱싱되어있다고 판정하면 되므로, 경우의 수 카운트만 맞다면 별도의 관리가 필요없다.
• 따라서 장면의 수는 결국 재귀호출의 호출 횟수로 귀결된다.
• 각 장면에는 적어도 한 명 이상의 배우가 필요하므로, 재귀함수의 종료 조건은 배우가 0일 때이다.
• K는 2^N - 1의 공식을 통해 구할 수 있다. 위의 조건과 마찬가지로 배우가 한 명도 없을 때는 카운트할 필요가 없기에 1을 빼준다.
  • 예제의 경우 배우가 2명이기에, 11 10 01 00의 네 가지 경우의 수를 가지고 있으나, 00인 경우는 카운트할 필요가 없기에 K는 3이다.