[일반] [1023 괄호문자열] DP 점화식 찾는 것좀 도와주십쇼..

[ㅇd(39.119)]

https://www.acmicpc.net/problem/1023

문제의 풀이 방향은 알고 있습니다. 

1. 괄호 ㄴㄴ 문자열의 개수를 세는 DP 알고리즘을 설계하고

2. 구해놓은 DP값들을 트래킹해서 답을 만들면 되지 않습니까.

그런데 1번에서 그냥 막혀버렸습니다. ㅋㅋ

제 지능으로는 납득이 되는 점화식을 짤수가 없네요..

혹시 점화식을 어떻게 짜야할지 방향성을 알려주실수 있으신가요?

살려주십쇼 고수님덜

[Gravekper(gravekper)]

길이가 n인 잘못된 문자열 갯수를 세는 것보다 길이가 n인 괄호 문자열 갯수를 찾아서 2^n에서 빼는게 편할걸

[익명(223.39)]

답변해주셔서 감사합니다! 고민결과 2번 트래킹과정을 수행하기 위해서는 dp에 prefix의 상태가 포함되어야한다는 걸 깨달아서 아마 말씀드린 방식으로는 1번 과정은 구할수 있지만 2번 과정은 못구할것같다고 생각이 들어요. 아무튼간 시간내서 답변해주셔서 감사합니다. - dc App

[익명(14.6)]

어케푸냐 이문제

[익명(39.7)]

괄호 (를 +1, )를 -1이라거 했을때 Dp[i][j] = 현재 값이 j이고 i개의 괄호 문자열로 힌번도 음수가 되지 않고 0을 만드는 경우의 수

[익명(223.39)]

감사합니다. 아마 이방법으로 시도해볼것같습니다. - dc App

[즈우북(121.161)]

트래킹을 굳이 따로할 필요가 없고, 묘지기님 말씀하신 방식으로 개수 세는것만 구현한 다음에 맨 앞글자부터 DP 써서 결정해나가면 됨. 앞에서 x개 문자가 고정됐을 때 괄호 ㄴㄴ 문자열 개수를 알면, 맨 앞에 글자가 '('일 때 경우의 수가 몇 갠지도 알 수 있음. '('일 때 개수가 k개보다 작으면 k에서 그 값 빼고 맨 앞 글자를 ')'로 고정하고 다음 단계로 건너가면 되고, 그게 아니면 맨 앞 글자 '('로 하고 다음 위치에서 재귀적으로 같은 과정 반복하면 됨

[익명(223.39)]

네 맞습니다. 그 과정을 저는 트래킹이라고 말한거였는데, 오해를 불러일으키는 표현이었던것같네요. 긴 답변 감사합니다. - dc App

[익명(121.150)]

전 이거 이분 탐색으로 풀었어요

[익명(121.150)]

이분탐색 + dp