an3735297   2년 전

길이가 N개인 문자열이 있을 때 길이가 N+2 의 문자열은

1. ____() 

2. ()____

3.(_____)

이렇게 3가지 경우로 늘릴 수 있다고 생각했습니다.

그리고 1번과 2번에서 ()___() 처럼 생기면 중복이 발생하기 때문에 ()___() 인 문자열은 빼줬습니다.

결론적으로 점화식은 A(n) = A(n-2) * 3 - A(n-4) 

라고 생각했습니다.

하지만 답은 틀렸기 때문에 잘못된 풀이인것 같은데 혹시 어디서 틀렸다고 지적해주실 수 있나여.

WeissBlume   2년 전

(___)(___), (__)(___), (_)(____), ... <- 이런 형태도 가능합니다

an3735297   2년 전

아~ 감사합니다 ㅎㅎㅎ

112vustjd   7달 전

길이가 N개인 모든 괄호 문자열을 A(N)

길이가 N개인 하나의 괄호로 이루어진 괄호 문자열을 B(N)이라고 하면

A(N+2)=A(N)+A(N)*B(2)+A(N-2)*B(4)+A(N-4)*B(6)..........A(N-2k)*B(2k)..........A(2)*B(N)

B(N+2)=A(N)

가 성립합니다.

댓글을 작성하려면 로그인해야 합니다.