문제풀이
- '('를 1, ')'를 -1의 가중치를 두고 dp[현재까지의 가중치] = 경우의 수로 둔다.
- S를 순회하며 dp테이블을 채워나간다.
주의사항
소요시간
10분
package AtCoder.ProblemList.Difficulty800_1199.CountBracketSequences
const val MOD = 998244353
fun main() {
val S = readln().trim()
val prev = IntArray(1501).apply { this[0] = 1 }
val next = IntArray(1501)
for (c in S) {
when (c) {
'(' -> {
for (i in 0 until (prev.size - 1)) {
next[i + 1] = prev[i]
}
}
')' -> {
for (i in 1 until prev.size) {
next[i - 1] = prev[i]
}
}
'?' -> {
for (i in prev.indices) {
if (i > 0) next[i - 1] = (next[i - 1] + prev[i]) % MOD
if (i < (prev.size - 1)) next[i + 1] = (next[i + 1] + prev[i]) % MOD
}
}
}
for (i in prev.indices) {
prev[i] = next[i]
next[i] = 0
}
}
println(prev[0])
}