블로그 옮겼습니다

\(1\leq{N}\leq{50}\)\(0\leq{K}\lt{2^N-1}\)괄호 문자열(correct parenthese sequence)의 정의는 이미 잘 알려져 있다.그리고 어떤 문자열 S가 '(' 와 ')' 로만 이루어져있는데 괄호 문자열이 아니라면 이것을 괄호ㄴㄴ문자열이라고 정의한다.N과 K가 주어진다. 길이가 N인 괄호ㄴㄴ문자열들을 사전순으로 정렬했을 때 K번째인 문자열을 찾는 문제이다.인덱스는 0부터 시작한다는 것에 주의하자. 우선 괄호 문자열의 개수를 구하는 방법을 알아보자.dp[i][j] : 이미 i개의 문자가 정해졌고 짝이 지어지지않은 열린 괄호의 수가 현재 j 개일 때 괄호 문자열의 수dp[i][j] = dp[i-1][j] + dp[i-1][j+1]왜냐하면 각각의 위치에서는 괄호를 열거..

\(2\leq{len}\leq{2500}\) 이 문제는 길이 len 의 correct parentheses sequence 가 주어졌을 때 왼쪽에 있는 '열린 괄호'를 하나와 임의의 위치에 있는닫힌 괄호 하나, 총 두개를 지우는 행위를 빈 문자열이 될 때 까지 반복하는 방법의 수를 구하는데, 지울 때 마다 지운 직후에도 correct paranthese sequence 이도록 지우는 방법의 수를 구하는 문제이다. 우선 이 문제를 좀 더 간단하게 바꿔보자. 왼쪽에서부터 열린괄호 하나와 닫힌괄호 하나를 지워나가는 것은 결국열린괄호 하나와 닫힌괄호 하나를 매칭시키는 것과 같다고 볼 수가 있다. 물론 한 쌍을 지워도correct parentheses sequence 이도록 말이다. 그럼 주어진 제약조건을 만족하..