[Python] 17623번 괄호

https://www.acmicpc.net/problem/17623

---

 

24/07/01

 

 

업다운 랜디를 하다가 만난 문제이다. 복습 겸 의식의 흐름대로 적어보고자 한다.

---

 

문제 접근 방식:

 

 

요구 사항은 다음과 같다.

 

괄호 문자열은 소괄호, 중괄호, 대괄호로 만들 수 있음.
괄호 문자열은 두 괄호 문자열을 서로 Concatenate하거나 하나의 괄호 문자열을 감싸면 만들 수 있음.
val함수를 통해 괄호 문자열의 값을 정수로 알 수 있음.
또한 dmap함수를 통해 괄호 문자열의 값을 정수로 알 수 있음.
어떤 정수 $N$이 주어질 때, $val(x) = N$이 되도록 하는 괄호 문자열 $x$를 찾는 것이 우리의 목적임.
이러한 $x$가 여러 개 있다면 $dmap(x)$가 최소가 되도록 하는 것이 우리의 목적임.

 

dmap함수는 (, ), {, }, [, ]를 각각 1, 2, 3, 4, 5, 6에 대응시켜 하나의 숫자를 만드는 함수이다.

 

예를 들자면 ()()[]라는 괄호 문자열은 121256이라는 숫자로 바뀐다.

 

val함수의 계산은 다음과 같다.

 

1. Z = XY인 경우, val(Z) = val(X) + val(Y)

2. X가 소, 중, 대괄호로 각각 둘러싸여 있는 경우, val((X)) = 2val(X), val({X}) = 3val(X), val([X]) = 5val(X).

 

이런 val함수의 계산법 때문에 일반적으로 정수 $N$이 주어지면 괄호 문자열이 여러 개가 될 수 있다는 점은 쉽게 알 수 있다.(문제에서도 언급되어 있다.)

 

dmap함수값이 작으려면, 되도록 괄호 문자열의 길이가 짧아야 할 것이다.

 

여기까지 문제 풀 때 생각을 하고, 그 이후의 생각은 다음과 같았다.

 

$\rightarrow$ dmap함수값이 작도록 하려면 어떻게 해야할까, 그리디로 해야할까?

 

$\rightarrow$ 제한을 보니 $N$의 크기가 $1,000$까지밖에 안되서 굳이 그럴 필요는 없을 것 같다. 그리고 더 이상의 그리디적 접근도 떠오르지 않는다. 

 

$\rightarrow$ $N$을 val값으로 가지는 괄호 문자열은 여러 개 있겠지만, 그 문자열의 부분 괄호 문자열의 val값이 모두 $N$보다 작다.

 

$\rightarrow$ 다시 말해서 항상 이전 상태로 부터 다음 상태가 만들어진다.

 

$\rightarrow$ 그래서 DP인건 당연하고, $N$을 만들 수 있는 이전 상태들은 $N$이 5로 나눠지는지, 3으로 나눠지는지, 2로 나눠지는지 체크하고 나눠진다면 그 상태에 대괄호, 중괄호, 소괄호를 각각 밖에 둘러썬 상태를 가능한 상태로 고려, $1+(N-1)$부터 $(N-1)+1$까지 이전 상태들을 두 개 붙인 상태들을 모두 고려해서 그 상태들 중 실제로 가장 작은 dmap값을 가지는 DP를 돌려보면 된다.

(맨 처음에 풀었을 때는 이전 상태를 두 개 붙인 상태를 모두 고려하지 않고, 소괄호 중괄호 대괄호를 덧붙인 상태만 고려해서 틀렸다.)

 

$\rightarrow$ min함수의 key값을 dmap함수로 주면 쉽게 구현할 수 있다.

 

$\rightarrow$ AC. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 17623번 괄호
# 그래프 탐색, DP
'''
요구 사항:
어떤 특정한 정수의 값이 되는 괄호문자열을 찾는다.
근데 그 괄호 문자열은 되도록 짧아야 하고,
길이가 같다면 소괄호 중괄호 대괄호 순으로 오면 좋음
접근 방법:
어떤 특정한 정수를 보자.
이 정수가 만약 2나 3이나 5로 나뉜다면?
예를 들어, 30이라고 해봐.
그러면 2, 3, 5로도 다 나뉘어지잖아.
일단 5로 나눠봐
[6]
6을 만들 수 있는 가장 작은 괄호 문자열?
()[[]]
근데 뭐가 최적인지 잘 모르겠음...
그래프 탐색을 하면 시간초과가 날까?
'''
import sys
input = sys.stdin.readline

b_to_d = {'(':'1', ')':'2', '{':'3', '}':'4', '[':'5', ']':'6'}
def dmap(bra):
    Y = ''
    for b in bra: Y += b_to_d[b]
    return int(Y)

min_bra = {1: '()', 2: '{}', 3: '[]', 4: '()[]'}
def find_min_bra(i):
    if i in min_bra:
        return min_bra[i]
    OK = []
    if i % 5 == 0:
        OK.append('['+find_min_bra(i//5)+']')
    if i % 3 == 0:
        OK.append('{'+find_min_bra(i//3)+'}')
    if i % 2 == 0:
        OK.append('('+find_min_bra(i//2)+')')
    for j in range(1, i//2 + 1):
        OK.append(min_bra[i-j]+min_bra[j])
        OK.append(min_bra[j]+min_bra[i-j])
    min_bra[i] = min(OK, key = dmap)
    return min_bra[i]
for i in range(5, 1001):
    find_min_bra(i)

for _ in range(int(input())):
    print(min_bra[int(input())])