10422번 - 괄호
길이가 N개인 문자열이 있을 때 길이가 N+2 의 문자열은
1. ____()
2. ()____
3.(_____)
이렇게 3가지 경우로 늘릴 수 있다고 생각했습니다.
그리고 1번과 2번에서 ()___() 처럼 생기면 중복이 발생하기 때문에 ()___() 인 문자열은 빼줬습니다.
결론적으로 점화식은 A(n) = A(n-2) * 3 - A(n-4)
라고 생각했습니다.
하지만 답은 틀렸기 때문에 잘못된 풀이인것 같은데 혹시 어디서 틀렸다고 지적해주실 수 있나여.
(___)(___), (__)(___), (_)(____), ... <- 이런 형태도 가능합니다
아~ 감사합니다 ㅎㅎㅎ
길이가 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)
가 성립합니다.
댓글을 작성하려면 로그인해야 합니다.
an3735297 2년 전
길이가 N개인 문자열이 있을 때 길이가 N+2 의 문자열은
1. ____()
2. ()____
3.(_____)
이렇게 3가지 경우로 늘릴 수 있다고 생각했습니다.
그리고 1번과 2번에서 ()___() 처럼 생기면 중복이 발생하기 때문에 ()___() 인 문자열은 빼줬습니다.
결론적으로 점화식은 A(n) = A(n-2) * 3 - A(n-4)
라고 생각했습니다.
하지만 답은 틀렸기 때문에 잘못된 풀이인것 같은데 혹시 어디서 틀렸다고 지적해주실 수 있나여.