괄호 문자열 표기법 (Small)

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

요약

각 N에 대해 재귀적으로 정의된 값이 N이 되는 가장 짧은 괄호 문자열을 찾고, 길이가 같으면 사전 순으로 가장 앞선 것을 출력한다.

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

문제

괄호 문자열은 다음과 같은 3개의 조건만으로 만들 수 있는 문자열을 말한다.

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

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

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

빈 문자열이 나타내는 값은 1이다.
괄호 문자열 a가 나타내는 값이 x라 할 때, (a)가 나타내는 값은 x + 1이다.
두 괄호 문자열 a, b가 나타내는 값이 각각 x, y라 할 때, a**b가 나타내는 값은 x × y이다.

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

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

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

입력

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

둘째 줄부터 각 테스트 케이스 별로 한 줄에 하나씩 자연수 N이 주어진다. (2 ≤ N ≤ 1,000,000 = 106)

출력

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

예제2

예제 1

입력

예상 출력

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

예제 2

입력

예상 출력

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