괄호

괄호문자열의 갯수를 세는 문제다. 경우의 수를 세는 문제는 완전탐색류의 문제라고 생각하면 될 것 같다. 그리고 완전탐색은 DP로 해결하는 경우를 생각할 수 있다.

우선 괄호문자열은 쌍으로 존재하므로, 홀수인 경우 무조건 0인 것을 알 수 있다. 그리고 나머지의 경우들을 어떻게 세어야 할까 고민을 해보면 된다.

괄호문자열의 특징을 생각해보면, 무조건 열고 닫혀야 됨을 알 수 있다.

그리고 2개, 4개, 6개 짜리를 생각해보면

• 2개
  - ()
• 4개
  - (())
  - ()()
• 6개
  - ((()))
  • (()())
  • (())()
  • ()()()
  • ()(())

맨 처음에 나는 ()를 하나의 그룹으로 생각하고 최대 문자열의 길이/2 만큼의 그룹을 하나씩 만들어가면서 그 안에 필요한 괄호의 숫자들을 넣는 것을 생각했다.

예를 들어, 6개의 경우

• (?)
• (?)(?)
• (?)(?)(?)

이렇게 1개, 2개, 3개의 그룹을 늘려가면서 ?를 채우면 되는 것으로 생각했다.

(?)는 ?안에 4개의 괄호문자열 경우의 수를 넣으면 되고, (?)(?)는 각각 0, 2개의 괄호문자열 경우의 수 조합을 나열하면 된다.

이러면 경우의 수를 세는 방법이 복잡해지는데, 조금더 생각해보니 맨 앞에 올 수 있는 괄호의 조합을 고정시키고 나머지 문자열의 갯수로 만들 수 있는 경우의 수를 곱하면 해결할 수 있음을 깨달았다.

즉, 6개의 경우

• (4) * 0개로 만들 수 있는 경우의 수
• (2) * 2개로 만들 수 있는 경우의 수
• (0) * 4개로 만들 수 있는 경우의 수

이 생각까지 도달하여 코드를 구현하면 된다.

답

package main

import (
	"bufio"
	"os"
	"strconv"
)

var (
	sc *bufio.Scanner
	wr *bufio.Writer
)

func init() {
	sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	wr = bufio.NewWriter(os.Stdout)
}

func scanInt() int {
	sc.Scan()
	ret, _ := strconv.Atoi(sc.Text())
	return ret
}

const Mod = 1000000007

func main() {
	dp := make([]int, 5001)

	dp[0] = 1
	dp[2] = 1

	for l := 4; l <= 5000; l += 2 {
		for n := l-2; n >= 0; n -= 2 {
			dp[l] += dp[n] * dp[l-n-2]
			dp[l] %= Mod
		}
	}

	tc := scanInt()
	for tci := 0; tci < tc; tci++ {
		l := scanInt()
		if l%2 == 0 {
			wr.WriteString(strconv.Itoa(dp[l]))
		} else {
			wr.WriteByte('0')
		}
		wr.WriteByte('\n')
	}

	wr.Flush()
}