시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 1024 MB | 267 | 52 | 24 | 13.793% |
괄호 문자열은 다음과 같은 3개의 조건만으로 만들 수 있는 문자열을 말한다.
(
a)
는 괄호 문자열이다.괄호 문자열의 예시로는 (())()
, (((()())())())
, ((()())()()())(())
등이 있다.
다음과 같은 방법으로 괄호 문자열이 나타내는 값을 정한다.
(
a)
가 나타내는 값은 x + 1이다.예를 들어 (())()
는 6을 나타낸다.
()
는 1 + 1 = 2를 나타낸다.(())
는 2 + 1 = 3을 나타낸다.(())()
는 3 × 2 = 6을 나타낸다.자연수 N이 주어지면 N을 나타내는 가장 짧은 괄호 문자열을 구해보자. 단, 그러한 문자열이 여러 개 있으면 사전 순으로 가장 앞서는 것을 구한다.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 20)
둘째 줄부터 각 테스트 케이스 별로 한 줄에 하나씩 자연수 N이 주어진다. (2 ≤ N ≤ 1,000,000 = 106)
첫째 줄부터 각 테스트 케이스 별로 한 줄에 하나씩 N을 나타내는 가장 짧은 괄호 문자열을 출력한다. 단, 그러한 문자열이 여러 개 있으면 사전 순으로 가장 앞서는 것을 출력한다.
3 6 23 123
(())() (((()())())()) ((()())()()())(())
6 987997 9879 98799 98 987 9
((((((()()()()()()()())()())(()())())())()())(())()()) ((((()()()())()()())(())())()())(()) ((((()()()()()()()())()())()()())()())(()) ((())()()()())() (((()())()()())()()())(()) (()()())