카탈란 수 (1) 썸네일형 리스트형 백준 10422 - 괄호 www.acmicpc.net/problem/10422 짝이 맞는 괄호의 개수는 카탈란 수의 잘 알려진(Well Known) 예시 중 하나이다. 카탈란 수에 대해 자세한 정보는 이 글에 있으며 $\binom{2n}{n} - \binom{2n}{n - 1} = \frac{1}{n + 1} \binom{2n}{n} = \frac{(2n)!}{(n + 1)!n!}$ 다음과 같이 3개의 식으로 사용할 수 있다. 이 문제에서는 1,000,000,007로 나눈 나머지를 구해야 하므로 페르마의 소정리를 활용하기 위해 3번째 식을 이용했다. 주의 사항은 n쌍이 아니라 n개가 입력으로 주어지므로 괄호의 개수가 홀수개일 때는 괄호 짝이 절대 만들어지지 않는다는 점과 짝수개가 주어지면 이를 괄호의 짝 개수로 치환하기 위해 2.. 이전 1 다음
