문제풀이
- dp[문자열의 길이][열린 괄호의 개수 - 닫힌 괄호의 개수] = 경우의 수로 두고 dp테이블을 채워나간다.
- 단, 열린 괄호의 개수 - 닫힌 괄호의 개수가 음수가 되는 경우는 고려하지 않는다.
- N개의 문자를 결정하는데, 앞에서 부터 차례대로 열린 괄호를 넣었을때 경우의 수를 고려하며 채워나간다.
주의사항
- Long타입을 사용해야 한다.
소요시간
1시간
package 백준.Platinum.P3.p1023_괄호문자열
const val EMPTY = -1L
const val IMPOSSIBLE = Int.MIN_VALUE shr 2
fun main() {
val (N, K) = readln().trim().split(" ").let { it[0].toInt() to it[1].toLong() }
val dp = Array(N + 1) { LongArray(N + 1) { EMPTY } }
fun dp(n: Int = N, state: Int = 0): Long {
if (n == 0) return if (state == 0) 1 else 0
if (dp[n][state] != EMPTY) return dp[n][state]
dp[n][state] = dp(n - 1, state + 1) + (if (state > 0) dp(n - 1, state - 1) else 0)
return dp[n][state]
}
fun result(n: Int = N, state: Int = 0, k: Long = K): String {
if (n == 0) return ""
val count = (1L shl (n - 1)) - (if (state == IMPOSSIBLE) 0 else dp(n - 1, state + 1))
return if (k < count) "(" + result(n - 1, if (state == IMPOSSIBLE) IMPOSSIBLE else state + 1, k)
else ")" + result(n - 1, if (state == 0 || state == IMPOSSIBLE) IMPOSSIBLE else state - 1, k - count)
}
if (K < (1L shl N) - dp()) println(result())
else println(-1)
}