내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
올바른 괄호의 갯수
ps:problems:programmers:12929
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 올바른 괄호의 갯수 ====== * 카탈랑 수를 해로 갖는 대표적인 문제 ===== 풀이 ===== * 마지막 위치에는 닫는괄호(**)**)가 와야 한다. 이 괄호와 매칭되는 여는 괄호(**(**)가 i번째에 있는 경우들로 나눠서 생각할 수 있다. * 매칭되는 괄호가 i번째에 있으면.. * <code> ....(....) i n </code> * [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)에 계산이 가능하다. [[:ps:카탈랑 수]] 참고 ===== 코드 ===== <dkpr py> """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) </dkpr> {{tag>프로그래머스 ps:problems:programmers:Level_4}}
ps/problems/programmers/12929.txt
· 마지막으로 수정됨: 2021/01/22 06:37 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로