처음부터 끝까지 풀이를 보지 않고 직접 구현해냈기 때문에, 기분이 좋아서, 오랜만에 기념삼아 블로그 글을 쓰게되었다.

문제 제목 : 괄호
문제 링크 : https://www.acmicpc.net/problem/10422

문제 이해

전체 테스트 케이스의 수 T와 괄호 문자열의 길이 L이 주어진다. 길이가 L인 올바른 괄호 문자열의 개수를 출력하시오.

일단 기본적으로 괄호 문자열이 완성되기 위해서는 L이 홀수 일때는 무조건 0이다.

풀이

L이 항상 홀수일때는 올바른 괄호 문자열의 개수가 0이므로, N을 L/2이라고 정의하겠다.
따라서 L이 2일 때는 N이 1, L이 4일 때는 N이 2이다.

N이 1일 때부터 4까지 나열해보면

# n = 1

()

-> 1개

# n = 2

()()
(())

-> 2개

# n = 3

()()()
(())()
()(())
(()())
((()))

-> 5개

# n = 4

()()()()
(())()()
()(())()
(()())()
((()))()
()()(())
(())(())
()((()))
()(()())
(()()())
((())())
(()(()))
((()()))
(((())))

-> 14개

위와 같다.

모든 표현할 수 있는 괄호쌍은 아래 기준으로 나눌 수 있는데

1. 두 개 이상의 괄호쌍으로 나눌 수 있는 경우
2. 두 개 이상의 괄호쌍으로 나누는 것이 불가능한 경우

위 상황에 따라 모든 괄호쌍을 나누어보면

1번 상황에서는 어떤 괄호쌍 뒤에 특정 괄호쌍이 붙어서 만들어진 괄호문자열이고
2번 상황에서는 전체가 새로운 괄호쌍으로 이루어진 경우이다.

따라서

f(n)일 때

1번 상황인
f(n-1) 에 뒤에 () 2개의 괄호로 이루어진 괄호쌍이 붙은 경우
f(n-2) 에 뒤에 (()) 4개의 괄호로 이루어진 괄호쌍이 붙은 경우
f(n-3) 에 뒤에 ((())), (()()) 6개의 괄호로 이루어진 괄호쌍이 붙은 경우
.
.
.
즉 이 경우에서는 총 개수가 f(N-i) * f(i)개 라고 볼 수 있다.

2번 상황인
전체가 분해할 수 없는 하나의 괄호쌍으로 이루어진 경우는 항상
f(n-1)의 모든 괄호문자열을 또 다른 하나의 괄호로 덮는 경우
(ex, (~~~) (~*~) 등)
즉 이 경우는 총 개수가 f(n-1)개 라고 볼 수 있다.

으로 분석할 수 있다.

위 분석 결과에 따라 N이 4일때를 분석해보면 아래와 같이 성립하는 것을 확인할 수 있다.

()()() ()
(())() ()
()(()) ()
(()()) ()
((())) ()

-> N=3 뒤에 () 가 붙은 것


()() (())
(()) (())

-> N=2 뒤에 (()) 가 붙은 것


() ((()))
() (()())

-> N=1 뒤에 ((())), (()()) 가 붙은 것


( ()()() )
( (())() )
( ()(()) )
( (()()) )
( ((())) )

-> N=3 양 옆에 괄호가 붙어서 새로운 독립적인 괄호문자열이 생긴 경우

결론적으로 공식을 내보면

f(1) = 1
f(N) = {f(N-1) * f(1) + f(N-2) * f(2) + ... + f(1) * f(N-1)}  +  f(N-1)

이라는 공식을 낼 수 있다.

위 공식에 따라 1,000,000,007로 나누는 것과, 자료형의 범위를 넘어가서 오버플로우가 나는 것만 유의해서 풀면 된다.

코드

코드 : Github