시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 512 MB119749537439.368%

문제

6개의 문자 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’ 로 이루어진 올바른 괄호 문자열 W에 대하여 정수의 ‘괄호값’을 지정하는 함수 val(W)가 정의되어 있다. 먼저 올바른 괄호 문자열부터 정의해보자.

한 쌍의 괄호로 구성된 길이 2인 문자열, 즉 ‘()’, ‘[]’, ‘{}’은 모두 올바른 괄호 문자열이다. 이것을 단위 괄호라고 한다. X, Y가 올바른 괄호 문자열인 경우, 아래와 같은 작업을 통하여 만들어지는 새로운 문자열은 모두 올바른 괄호 문자열이 된다.

  1. XY // 올바른 두 괄호 문자열의 접합(concatenation).
  2. (X), {X}, [X] // 올바른 괄호 문자열 전체를 다시 괄호로 감쌈.

올바른 괄호 문자열과 아닌 예가 다음에 있다. 단 괄호 문자 사이에 공백은 없다.

  • 올바른 예: ({}{}[(())]), (()), {}[][(())]
  • 올바르지 못한 예: {[(())], (([)])), {{{}}(), )]{}

이제 괄호값 val()의 계산 방법을 설명한다. 3 종류의 단위 괄호 (), {}, []의 괄호값은 각각 1, 2, 3으로 정의되어 있다. 즉 문자열이 X=‘()’, Y=‘{}’, Z=‘[]’이면 val(X) = 1, val(Y) = 2, val(Z) = 3이다. 만일 X, Y가 올바른 문자열이라고 할 때 이 둘을 순차적으로 연결한 문자열 Z=XY의 괄호값은 다음과 같이 계산된다.

  • val(Z) = val(X) + val(Y)

만일 어떤 올바른 문자열 XA=‘(X)’, B=‘{X}’, C=‘[X]’와 같이 (), {}, []로 둘러싸여 있을 경우에 A, B, C의 괄호값은 다음과 같이 계산된다.

  • val(A) = 2·val(X), val(B) = 3·val(X), val(C) = 5·val(X)

그런데 괄호값이 k인 문자열은 유일하지 않다. 예를 들어 ‘[]’, ‘{}()’, ‘()()()’ 모두는 괄호값이 3을 가지는 문자열이다. 다음 표는 올바른 괄호 문자열에 대응하는 괄호값 val(X)의 예를 보여준다.

올바른 괄호 문자열 X val(X)
(()()) 2(1+1) = 4
[[[]]] 3×5×5 = 75
[][][]{()} 3+3+3+3(1) = 12
((())[{}])() 2(2+5×2)+1 = 25

올바른 괄호 문자열 X를 숫자로도 표현할 수 있다. 괄호 문자열을 숫자로 바꾸는 방법은 각 괄호 문자에 대하여 아래 표와 같이 1에서 6까지의 숫자로 대치해 십진수로 읽은 값이다.

문자 ( ) { } [ ]
대치문자 1 2 3 4 5 6

괄호 문자열 X를 위에 설명한 방식으로 변환시킨 값을 dmap(X)로 표시한다. 몇몇 올바른 괄호 문자열 X에 대해서 dmap(X)을 나타낸 표가 아래에 있다.

val(R)=3 문자열 dmap(R)
()()() 121212
{}() 3412
(){} 1234
[] 56
val(R)=4 문자열 dmap(R)
({}) 1342
()()()() 12121212
()[] 1256
{}{} 3434

여러분은 주어진 정수 N에 대하여 val(X) = N을 만족하는 올바른 괄호 문자열 중에서 dmap(X) 값이 최소X를 찾아서 출력해야 한다. 출력 문자열은 공백 없이 괄호 문자로만 구성되어야 한다.

입력

첫 번째 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 100) 두 번째 줄부터 T+1번째 줄까지 한 줄에 하나씩 정수 N이 주어진다. (5 ≤ N ≤ 1,000)

출력

각 테스트케이스마다 val(X) = N을 만족하는 올바른 괄호 문자열 X 중에서 dmap(X)가 최소인 문자열을 찾아서 한 줄에 하나씩 공백 없이 출력한다.

서브태스크 1 (17점)

  • N ≤ 10

서브태스크 2 (48점)

  • N ≤ 1,000

이 서브태스크에서는 dmap값을 최소화하지 않아도 점수를 받을 수 있다. 구체적으로, 입력에 대한 최적해 X와 여러분이 구한 결과를 Y라 할 때 점수는 다음의 공식에 의해 주어진다.

  • 하나의 출력에서라도 Y가 올바른 괄호문자열이 아니거나, val(Y) ≠ N인 경우: 0점
  • 그 외: (모든 입력 데이터에 대한 |X|/|Y|의 최솟값) × 48점 (단, |X|는 문자열 |X|의 길이)

서브태스크 3을 해결하는 코드는 서브태스크 2도 해결할 수 있다.

서브태스크 3 (35점)

원래의 제약조건 이외에 아무 제약조건이 없다.

예제 입력 1

1
5

예제 출력 1

{}[]

예제 입력 2

3
11
22
33

예제 출력 2

()[{}]
(()[{}])
([[]])[]

채점 및 기타 정보

  • 예제는 채점하지 않는다.