괄호(bracket) > 문제은행



문제은행

3435 : 괄호(bracket)

제한시간: 0Sec    메모리제한: 0mb
해결횟수: 0회    시도횟수: 0회    채점준비중입니다.



6개의 문자 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’ 로 이루어진 올바른 괄호 문자열 에 대하여 정수의 

‘괄호값’을 지정하는 함수 val(W)가 정의되어 있다. 먼저 올바른 괄호 문자열부터 정의해보자. 

 

한 쌍의 괄호로 구성된 길이 2인 문자열, 즉 ‘( )’, ‘[ ]’, ‘{ }’은 모두 올바른 괄호 문자열이다. 

이것을 단위 괄호라고 한다. X, Y가 올바른 괄호 문자열인 경우, 아래와 같은 

작업을 통하여 만들어지는 새로운 문자열은 모두 올바른 괄호 문자열이 된다.

 

1) XY              // 올바른 두 괄호 문자열의 접합(concatenation).

2) (X), {X}, [X] // 올바른 괄호 문자열 전체를 다시 괄호로 감쌈. 

 

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

 

 592d7a7e0c8d86d1da5cb1fdc052ff77_1563687 

 

이제 괄호값 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)​ ​

 

만일 어떤 올바른 문자열 X가 A=‘(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)​​의 예를 보여준다. ​ 

 

 592d7a7e0c8d86d1da5cb1fdc052ff77_1563687 

 

올바른 괄호 문자열 X를 숫자로도 표현할 수 있다. 괄호 문자열을 숫자로 바꾸는 방법

은 각 괄호 문자에 대하여 아래 표와 같이 1에서 6까지의 숫자로 대치해 십진수로 읽

은 값이다. ​ 

 

 592d7a7e0c8d86d1da5cb1fdc052ff77_1563687 

 

괄호 문자열 X를 위에 설명한 방식으로 변환시킨 값을 dmap(X)​​로 표시한다. 몇몇 

올바른 괄호 문자열 X에 대해서 dmap(X)​​​을 나타낸 표가 아래에 있다. 

 

 

 592d7a7e0c8d86d1da5cb1fdc052ff77_1563687 

 

여러분은 주어진 정수 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: 전체 점수 100점 중 17점에 해당하며 N ≤ 10.

* 부분문제 2: 전체 점수 100점 중 48점에 해당하며 N ≤ 1,000이다. 이 부분문제에서는 dmap 값을 
            최소화하지 않아도 점수를 받을 수 있다. 구체적으로, 입력에 대한 최적해 X와 여러분이 구한 결
            과를 Y라 할 때 점수는 다음의 공식에 의해 주어진다. 
                  - 하나의 출력에서라도 Y가 올바른 괄호문자열이 아니거나, val(Y) ≠ N인 경우 : 0점
                  - 그 외 : (모든 입력 데이터에 대한 |X| / |Y| 의 최솟값) * 48점 (단, |X|는 문자열 X의 길이)
             부분문제 3을 해결하는 코드는 부분문제 2도 해결할 수 있음에 유의하라.

* 부분문제 3: 전체 점수 100점 중 35점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다

[Copy]
1
5
[Copy]
{}[]


[Copy]
3
11
22
33
[Copy]
()[{}]
(()[{}])
([[]])[]






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.