목록k번째 dp (1)
블로그 옮겼습니다
BOJ 1023번 괄호 문자열
\(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]왜냐하면 각각의 위치에서는 괄호를 열거..
Algorithm/Problem Solving
2017. 5. 9. 13:37