17428번 - K번째 괄호 문자열

문제

괄호 문자열은 다음과 같이 정의한다.

• 빈 문자열은 괄호 문자열이다.
• S가 괄호 문자열일 때, (S)도 괄호 문자열이다.
• S와 T가 괄호 문자열이라면, ST도 괄호 문자열이다.
• 모든 괄호 문자열은 위의 3개 규칙으로만 만들 수 있다.

길이가 N인 괄호 문자열 중에 사전순으로 K번째인 문자열을 출력하는 프로그램을 작성하시오. 사전순으로 가장 앞서는 괄호 문자열은 0번째이다. ‘(‘가 ‘)’보다 사전순으로 앞선다.

입력

첫째 줄에 자연수 N과 K가 주어진다.

출력

첫째 줄에 K번째 괄호 문자열을 출력한다. K번째 괄호 문자열이 없는 경우에는 -1을 출력한다.

제한

• 2 ≤ N ≤ 50, N은 짝수
• 0 ≤ K ≤ 2^N-1

힌트