[백준 17623] 괄호

괄호(17623)

문제 출처 : https://www.acmicpc.net/problem/17623

 

이 문제는 2019년 정보올림피아드 2차 고등부 2번 문제 입니다.

 

괄호 문제들이 심심치 않게 출제되고 있기 때문에 어떻게 푸는지 감을 잡고 있어야 합니다. 이 문제는 특히나 생각할 부분이 많이 있습니다. 단순히 괄호만 계산하면 되는 것이 아니라 괄호 문자열을 숫자로 변경해서 가장 숫자가 낮은 형태로 저장해야 합니다.

괄호 문자열을 만드는 것은 DP로 해결이 가능해 보입니다. 그리고 dmap값을 통해 숫자로 변경하는 부분은 복잡하기는 하지만 그리 어려운 부분은 아닙니다.

문제 이해하기

X 찾기

올바른 문자열을 만드는 방법을 생각해 보겠습니다. solve(N)이라는 함수를 만들어 문자열 X를 찾는 것입니다. N값에 따라 X는 다양한 형태를 가질 수 있습니다. N 값이 30이라면 아래와 같이 표현할 수 있습니다.

• ( solve(30 // 2) )
• { solve(30 // 3) }
• [ solve(30 // 5) ]

괄호의 모양이 각기 다르다는 것을 주의해야 합니다. 이렇게 2, 3, 5 로 나누어진다면 N 값이 줄어들면서 괄호를 넣어 표현할 수 있습니다. 또한 2, 3, 5로 나누는 방법 외에도 아래와 같이 나타낼 수도 있습니다.

• solve(1) + solve(29)
• solve(2) + solve(28)
• …
• solve(29) + solve(1)

이런식으로 더해주는 방식으로도 표현이 가능합니다.

dmap 최소값 찾기

위와 같이 다양한 형태의 X를 찾은 뒤 dmap을 통해 최소값을 찾아야 합니다. 무작정 짧은 괄호가 낮은 값이 아닙니다. X의 괄호들을 숫자로 변환하여 그 값들을 비교해서 제일 최소값을 저장하면 됩니다. 이 부분은 알고리즘이 필요없이 구현만 하면 되기 때문에 아래 코드에서 알아보겠습니다.

코드 작성하기

그럼 문제를 직접 풀면서 해결해 보겠습니다.

입력 받기

T = int(input())

for _ in range(T):
    N = int(input())
    print(val(N))

먼저 테스트 케이스 T를 입력 받습니다. 다음으로 T개의 정수 N을 입력 받습니다. 입력받은 N을 통해 답을 찾아 출력합니다. val(X) = N을 만족하는 문자열 중에서 dmap(X)가 최소인 문자열을 찾아야 합니다.

solve 함수1

solve 함수는 N을 입력하면 문자열 X가 나오는 함수 입니다. 여기에 추가적으로 dmap 값이 최소인 형태까지 구현해야 합니다. 먼저 쉬운 부분 부터 하나하나 구현해 보겠습니다.

arr = (5, 3, 2)
bracket = ('[]', '{}', '()')

def solve(n):
    rst = []
    for i in range(len(arr)):
        if n % arr[i] == 0:
            tmp = bracket[i][0] + solve(n // arr[i]) + bracket[i][1]
            rst.append(tmp)

    for i in range(1, n):
        tmp = solve(i) + solve(n - i)        
        rst.append(tmp)  

    ans = min_dmap(rst)
    return ans

반복문은 크게 두 부분이 있습니다. 첫 번째 반복문에서는 5, 3, 2로 나누어 지는지 확인하는 부분 입니다. 만약 나누어 진다면 재귀 함수로 안을 구현 합니다. 그리고 양쪽에 5, 3, 2에 맞는 괄호로 감싸 줍니다. 그 값들을 rst라는 리스트에 넣어줍니다.

다음 반복문은 solve(1) 부터 solve(n - 1)까지 더해주는 형태 입니다. 이렇게 구한 값을 rst에 넣어줍니다.

rst에는 n이라는 숫자로 만들 수 있는 모든 괄호 문자열 X가 저장되어 있습니다. 그 X들 중 dmap의 최소값을 ans로 하여 하나의 값을 찾습니다.

solve 함수2

위 solve 함수는 종료조건도 없고, 메모이제이션 처리도 하지 않았습니다. 이제 종료조건과 메모이제이션 처리를 해보겠습니다.

dp = [0] * (1000 + 1)
dp[1] = '()'
dp[2] = '{}'
dp[3] = '[]'

arr = (5, 3, 2)
bracket = ('[]', '{}', '()')

def solve(n):
    if dp[n]:
        return dp[n]
    
    rst = []
    for i in range(len(arr)):
        if n % arr[i] == 0:
            tmp = bracket[i][0] + solve(n // arr[i]) + bracket[i][1]
            rst.append(tmp)

    for i in range(1, n):
        tmp = solve(i) + solve(n - i)        
        rst.append(tmp)  

    ans = min_dmap(rst)
    dp[n] = ans
    return ans

dp라는 리스트로 메모이제이션 처리를 합니다. dp의 크기는 범위의 최대값인 1000으로 하였습니다. N값이 얼마가 될 지 모르기 때문에 최대값으로 만들었습니다. 이러면 테스트 케이스가 많아도 이미 만들어진 내용은 다시 계산하지 않아도 됩니다.

종료 조건은 dp[1], dp[2], dp[3]으로 대신합니다. 해당 값이 이미 있기 때문에 solve() 함수의 처음에 있는 if문에서 처리가 됩니다. dp[n]값이 아직 없다면 계산 후 마지막에 저장이 됩니다.

dmap 계산

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

def min_dmap(arr):
    chk = float("INF")
    ans = ''
    for a in arr:
        tmp = dmap(a)
        if tmp < chk:
            chk = tmp
            ans = a
    return ans

dmap 함수는 괄호를 숫자로 변경하는 코드 입니다. 문자열로 Y값을 만든 다음에 숫자로 변경하려 리턴해 줍니다.

min_dmap은 X가 들어있는 리스트에서 dmap값을 확인하여 최소값을 찾는 로직입니다. 사실 min_dmap은 구현할 필요는 없습니다. min 함수의 key를 이용하면 쉽게 dmap의 최소값을 구할 수 있습니다. min 함수를 이용한다면 아래와 같이 넣어주면 됩니다.

    ans = min(rst, key=dmap)

min 함수에 익숙하지 않는 경우에는 min_dmap을 구현해보고, min 함수의 사용법도 익혀보시기 바랍니다.

전체 코드

전체 코드 입니다. 전체 코드에는 min 함수를 사용하는 코드로 작성하였습니다.

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

dp = [0] * (1000 + 1)
dp[1] = '()'
dp[2] = '{}'
dp[3] = '[]'

arr = (5, 3, 2)
bracket = ('[]', '{}', '()')

def solve(n):
    if dp[n]:
        return dp[n]
    
    rst = []
    for i in range(len(arr)):
        if n % arr[i] == 0:
            tmp = bracket[i][0] + solve(n // arr[i]) + bracket[i][1]
            rst.append(tmp)

    for i in range(1, n):
        tmp = solve(i) + solve(n - i)        
        rst.append(tmp)  

    ans = min(rst, key=dmap)
    dp[n] = ans
    return ans

T = int(input())

for _ in range(T):
    N = int(input())
    print(solve(N))