BOJ 17428 : K번째 괄호 문자열

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

17428번: K번째 괄호 문자열

걍 dp문제인데 재밌다.

dp[i][j] = 길이가 i이고, 완성되지 않은 괄호쌍이 j개일 때 만들 수 있는 괄호쌍 갯수

dp[i][j] = dp[i+1][j+1] ('('를 넣을 때) + dp[i+1][j-1] (')'를 넣을 때) 

 

문자열 구하는건 간단하다.

"'('를 넣을 때"와 "')'를 넣을 때"를 분리해서 K번째 문자열을 구해주면 된다.

코드