[BOJ] 1023번: 괄호 문자열

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

D[i][j] : prefix에서 )는 +1, (는 -1로 점수를 매겼을 때, prefix의 값이 j이고 길이 i이면서 괄호ㄴㄴ문자열인 갯수라고 정의합시다.(음수때문에 + 60을 해서 처리함)

예를 들어 D[2][60]은 ((  )(  )) 이 3가지 경우가 있으므로 3이고, D[3][62]는 prefix의 값이 2라는 소리니 ))XXX 와 같은 문자열을 생각하면 됩니다. (값은 8입니다.)

그러면 D[i][j]는 prefix에 ) 혹은 (를 추가하는 상황을 머릿속으로 생각해보면 D[i-1][j-1] + D[i-1][j+1]을 더하면 됩니다.

예를 들어 D[4][62], 즉 ))XXXX 에서 괄호ㄴㄴ문자열의 갯수는 )))XXX 에서 괄호ㄴㄴ 문자열의 갯수(D[3][63]) + ))(XXX 에서 괄호ㄴㄴ 문자열의 갯수(D[3][61])입니다.

이제 D 테이블을 채워나가면 되는데, 주의할 점은 j < 60일 경우 D[i][j]는 그냥 pow(2, i)를 바로 대입해주어야 합니다. 그렇지 않으면 실제로는 )( 나 ))(( 등이 괄호ㄴㄴ 문자열이 아님에도 불구하고 괄호ㄴㄴ문자열로 간주될 수 있기 때문입니다.

이렇게 D 테이블을 구한 이후에는 우선 입력받은 K가 D[N][60]보다 작은지 확인합니다. 만약 그렇지 않다면 바로 -1을 출력합니다.

이제는 주어진 K에 대응되는 문자열이 있음이 보장되니, 맨 앞자리부터 채워나가면 됩니다.

만약 )XXXX...X의 갯수가 K개보다 많으면 맨 앞자리가 )로 고정이 되고, 그렇지 않다면 cnt에 )XXXX....X의 갯수를 더해주고 맨 앞자리를 (로 두고, 뭐 이런식으로 반복하면 됩니다.

풀고 자야지 했는데 3시간이나 걸렸네요. D 테이블을 미숙하게 채워서 매우 오랫동안 고생했습니다.

https://github.com/blisstoner/BOJ/blob/master/1023.cpp