사용자 도구

사이트 도구


ps:problems:programmers:12929

올바른 괄호의 갯수

ps
링크https://programmers.co.kr/learn/courses/30/lessons/12929
출처프로그래머스
문제 번호12929
문제명올바른 괄호의 갯수
레벨Level 4
분류

수학

시간복잡도O(n)
인풋사이즈n<=14
사용한 언어Python
해결날짜2020/11/16
  • 카탈랑 수를 해로 갖는 대표적인 문제

풀이

  • 마지막 위치에는 닫는괄호())가 와야 한다. 이 괄호와 매칭되는 여는 괄호(()가 i번째에 있는 경우들로 나눠서 생각할 수 있다.
  • 매칭되는 괄호가 i번째에 있으면..
    • ....(....)
          i    n
    • [0:i]까지가 올바른 괄호로 채워져야 하고, [i+1:n]까지가 올바른 괄호로 채워져야지 전체가 올바른 괄호가 된다.
  • 즉 dp[i] * dp[n-i-1]이 이 경우의 올바른 괄호의 갯수이다
  • 이것을 모든 i에 대해서 합치면 dp[n] = dp[0]*dp[n-1] + dp[1]*dp[n-2] + … + dp[n-1]*dp[0] 를 얻는다.
  • 이 점화식은 카탈랑 수의 점화식이고, 카탈랑 수는 닫힌 형태로 표현해서 O(n)에 계산이 가능하다. 카탈랑 수 (Catalan number) 참고

코드

"""Solution code for "Programmers 12929. 올바른 괄호의 갯수".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12929
- Solution link: http://www.teferi.net/ps/problems/programmers/12929
"""

import math


def solution(n):
    return math.comb(2 * n, n) / (n + 1)

토론

댓글을 입력하세요:
C B Q B Z
 
ps/problems/programmers/12929.txt · 마지막으로 수정됨: 2021/01/22 06:37 저자 teferi