괄호 문자열 표기법 (Large)

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

요약

2 이상 10억 이하의 자연수 N이 주어질 때, 값이 N인 가장 짧은 괄호 문자열을 찾고 길이가 같으면 사전순으로 가장 앞선 것을 출력합니다.

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

문제

괄호 문자열은 다음 3개의 조건만으로 만들 수 있는 문자열이다.

빈 문자열은 괄호 문자열이다.
괄호 문자열 $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 10^9$ ).

출력

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

예제3

예제 1

입력

예상 출력

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

예제 2

입력

예상 출력

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

예제 3

입력

예상 출력

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