2018년 정보올림피아드 지역예선 중등부 15번 카탈란수 관련 문제 풀이

정답이 56이 나오는 문제였는데 지문에 정답이 없어서 이슈가 되었던 문제입니다.

올바른 괄호짝이 아닌 문자열이 모두 몇개인지 확인하려면 모든 경우의 수에서 올바른 괄호짝을 찾아서 그 경우를 빼 주면 되는 문제네요.

4개의 짝으로 만들 수 있는 경우- 즉 8개의 (,) 를 가지고 만들수 있는 모든 경우의 수는 8개의 괄호를 순서대로 나열 할 수 있는 모든 경우 8! 에서 ( 가 동일한 모양 4개 ) 가 동일한 모양 4개 이므로 4! * 4! 로 나눈 수가 전체의 경우의 수입니다.

따라서 나올수 있는 모든 경우의 수는 8!/(4!*4!)= 70 가지가 됩니다.

이제 올바른 괄호 짝을 구하는 방법을 찾아 보겠습니다.

이러한 규칙을 찾는 수열 중에 카탈란 수라고 불리우는 수열이 있습니다.

핀란드 수학자 카탈란의 이름을 단 수열이라고 하는데요. 이 수열을 이용하면 간단하게 찾을 수 있습니다.

1에서 n쌍의 괄호가 잘 짜놓는 방법의 수를 Cn 이라고 하면 C0,C1,C2...,Cn-1 을 이용하여 Cn 을 찾는 방법을 살펴 보겠습니다.

n-1쌍의 괄호가 잘 짜여진 것에 ()를 알맞은 곳에 넣어 주는 방법을 세면 됩니다.

(A)B와 같이 넣는다고 하면 A도 잘 짜여진 괄호가 되어 있어야 하고 B도 잘 짜여져 있어야 합니다.

만약 A에 괄호가 k쌍이 있다면 B에는 n-1-k 쌍이 있어야 합니다.(n-1 쌍의 괄호의 갯수이므로 A가 k쌍일때 B는 n-1-k쌍)

따라서 A와 B를 나누는 경우를 세면 됩니다.

따라서 다음과 같은 점화식을 얻을 수 있습니다.

C0=1 (괄호쌍이 없는 경우 1가지 존재)

C1=C0C0 (k=0,n-1-k = 0,k=0만 존재)

C2=C0C1 + C1C0

C3=C0C2 + C1C1 + C2C0

C4=C0C3 + C1C2 + C2C1 + C3C0

...

이렇게 계산해 보면 다음의 결과가 나오는 것을 확인 할 수 있습니다.

C0=1

C1=1

C2=1 + 1 = 2

C3=2 + 1 + 2 = 5

C4=5+2+2+5=14

따라서 정답은 70 - 14 = 56 입니다.

그 외에 카탈란수를 이용하여 구할 수 있는 경우는 다음과 같은 경우에 구할 수 있을것 같네요.

• n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것을 가리킨다. 예를 들면, 아래의 예제는 길이가 6인 모든 뒤크 단어들을 나열한 것이다. (XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY)

• n+2각형을 n개의 삼각형으로 나누는 방법의 수이다. 아래 그림은 6각형을 4개의 삼각형으로 나누는 모든 방법을 나타낸 것으로 총 ${\displaystyle C_{4}}$가지 이다.
• 이미지 출처 - https://ko.wikipedia.org/wiki/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98

정보올림피아드 문제 풀이 리스트 정리