title: "[프로그래머스] 올바른 괄호의 갯수 Python 파이썬 해설 (Level 4) - 이도훈"
cleanUrl: "programmers/12929"
description: "프로그래머스 Level 4 문제 [올바른 괄호의 갯수]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

from collections import Counter
from math import factorial

def find_combinations(n, state, combinations):
    if n < 0:
        return
    
    if n == 0:
        combinations.append(state[:])
        return
    
    start = 1 if len(state) == 0 else state[-1]
    for nextval in range(start, n+1):
        state.append(nextval)
        find_combinations(n-nextval, state, combinations)
        state.pop()
        
def mult(arr):
    s = 1
    for x in arr:
        s *= x
    return s
        
def solution(n):
    a, b = {}, {}
    a[1], b[1] = 0, 1
    
    for i in range(2, n + 1):
        # k (2 <= k <= i)개의 수를 합쳐서 i를 만드는 모든 경우의 수를 순회합니다.
        # 퇴각검색으로 구현합니다.
        state, combinations = [], []
        find_combinations(i, state, combinations)
        
        v = 0
        for comb in combinations:
            if len(comb) == 1:
                continue

            weight = factorial(len(comb)) / mult(factorial(cnt) for _, cnt in Counter(comb).items())
            v += mult(b[x] for x in comb) * weight
            
        a[i] = int(v)
        b[i] = a[i-1] + b[i-1]
        
    return a[n] + b[n]

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges