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)

만일 어떤 올바른 문자열 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)의 예를 보여준다.

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

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

은 값이다.

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

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

여러분은 주어진 정수 N에 대하여 val(X) = N 을 만족하는 올바른 괄호 문자열 중

에서 dmap(X) 값이 최소인 X를 찾아서 출력해야 한다. 출력 문자열은 공백 없이

괄호 문자로만 구성되어야 한다.

괄호(bracket) timer 2초 memory 512MB

괄호(bracket) 2초 512MB