괄호 문자열 표기법 (Small)

면접 대비

시간 제한1.5초메모리 제한1024 MB

요약

주어진 N에 대해 값이 N인 괄호 문자열 중 가장 짧은 것을 구하고, 길이가 같으면 사전순으로 앞서는 것을 고릅니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

괄호 문자열은 다음 세 가지 조건으로만 만들 수 있는 문자열이다.

빈 문자열은 괄호 문자열이다.
괄호 문자열 $a$ 에 대해 ( $a$ )는 괄호 문자열이다.
두 괄호 문자열 $a$ , $b$ 에 대해 $ab$ 는 괄호 문자열이다.

괄호 문자열의 예시로는 (())(), (((()())())()), ((()())()()())(()) 등이 있다.

다음 방법으로 괄호 문자열이 나타내는 값을 정한다.

빈 문자열이 나타내는 값은 1이다.
괄호 문자열 $a$ 가 나타내는 값이 $x$ 일 때, ( $a$ )가 나타내는 값은 $x + 1$ 이다.
두 괄호 문자열 $a$ , $b$ 가 나타내는 값이 각각 $x$ , $y$ 일 때, $ab$ 가 나타내는 값은 $x \times y$ 이다.

예를 들어 (())()는 6을 나타낸다.

()는 $1 + 1 = 2$ 를 나타낸다.
(())는 $2 + 1 = 3$ 을 나타낸다.
(())()는 $3 \times 2 = 6$ 을 나타낸다.

자연수 $N$ 이 주어지면 $N$ 을 나타내는 가장 짧은 괄호 문자열을 구한다. 그러한 문자열이 여러 개면 사전 순으로 가장 앞서는 것을 구한다.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. ( $1 \le T \le 20$ )

둘째 줄부터 각 줄에 자연수 $N$ 이 하나씩 주어진다. ( $2 \le N \le 1{,}000{,}000$ )

출력

각 테스트 케이스마다 $N$ 을 나타내는 가장 짧은 괄호 문자열을 한 줄에 하나씩 출력한다. 그러한 문자열이 여러 개면 사전 순으로 가장 앞서는 것을 출력한다.

예제2

예제 1

입력

예상 출력

(())()
(((()())())())
((()())()()())(())

예제 2

입력

예상 출력

((((((()()()()()()()())()())(()())())())()())(())()())
((((()()()())()()())(())())()())(())
((((()()()()()()()())()())()()())()())(())
((())()()()())()
(((()())()()())()()())(())
(()()())