7103 : 카탈란 수
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
n번째 카탈란 수 C_n을 구하는 프로그램을 작성하십시오.
카탈란 수는 다양한 조합론적 문제(올바른 괄호 문자열 개수, 다각형 삼각분할 개수 등)에서 나타나는 수열입니다.
공식:
카탈란 수는 다양한 조합론적 문제(올바른 괄호 문자열 개수, 다각형 삼각분할 개수 등)에서 나타나는 수열입니다.
공식:
C_n = C(2n, n) / (n + 1)입력 설명
첫째 줄에 정수 $n$이 주어집니다. ($0 \le n \le 30$)
출력 설명
$n$번째 카탈란 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5도움
C(2n, n)을 구한 후 n+1로 나누어 주면 됩니다. n=0일 때 C_0 = 1 임에 유의하십시오.