카탈란 수 Catalan number Python 구현
https://www.acmicpc.net/problem/10422
10422번: 괄호
‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러
www.acmicpc.net
이 문제를 풀면서 처음 알게된 수열이다.
뭐 위키피디아 같은데 보면 증명 다 볼 수 있는데, 코딩테스트에서 쓸 수 있을정도로만 알면 되니까 공식을 적는다.
Catalan(n) = 2n!/ ( n! * (n+1)! )
파이썬 코드는 다음과 같다.
import math
def catalan(n):
return math.factorial(2*n) // (math.factorial(n) * math.factorial(n+1))
1. 올바른 괄호 문자열의 갯수
https://www.acmicpc.net/problem/10422
10422번: 괄호
‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러
www.acmicpc.net
2. 정다각형의 삼각형 분할
https://www.acmicpc.net/problem/7737
7737번: 삼각분할
문제 삼각 분할이란 볼록 다각형의 대각선을 이용해서 삼각형으로 분할하는 것이다. 두 대각선은 교차할 수 없다. 삼각분할을 이루는 대각선의 집합이 다르면 두 삼각분할은 서로 다른 삼각분할이다. (꼭짓점에 1번부터 N번까지 번호를 붙인다) 오각형을 삼각분할하는 방법은 총 다섯가지가 있으며, 아래 그림과 같다. Tn을 n각형을 삼각분할하는 방법의 수라고 했을 때, T3 + T4 + ... + Tn을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n과 m이 주어
www.acmicpc.net
(물론 이걸로는 안풀리더라. 시간초과)
2-1. https://www.acmicpc.net/problem/1670
1670번: 정상 회담 2
첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다.
www.acmicpc.net
이 문제는 catalan(n//2) 를 하면 된다.
import math
import sys
def catalan(n):
return math.factorial(2*n) // (math.factorial(n) * math.factorial(n+1))
print(catalan(int(input())//2)%987654321)2-2 https://www.acmicpc.net/problem/17268
17268번: 미팅의 저주
인하대 컴퓨터 공학과에 재학 중인 이산이는 오랜만에 미팅을 나가 볼까 한다. 미팅은 N명이 원탁에 앉아서 진행된다고 한다. 질투가 난 이산이 친구 명기는 X의 저주를 걸었다. 그 저주는 N명이 동시에 2명씩 짝을 지어 악수할 때 사람의 팔이 교차되거나 한 사람이라도 악수를 하지 못하면 그 미팅은 실패하게 되는 저주다. 하지만 명기는 이산이에게 저주를 풀 기회를 주었다. 미팅에 성공할 경우의 수를 구하여 큰소리로 외치면 저주가 풀린다. 하지만 이산이는 계산
www.acmicpc.net
참고:
https://brilliant.org/wiki/catalan-numbers/
Catalan Numbers | Brilliant Math & Science Wiki
The Catalan numbers are a sequence of positive integers that appear in many counting problems in combinatorics. They count certain types of lattice paths, permutations, binary trees, and many other combinatorial objects. They satisfy a fundamental recurren
brilliant.org