BOJ 25321 - yo, i herd u liek ternary operators, so..

June 22, 2023

보자마자 카탈란 수같은 냄새가 났는데 예제가 불친절해서 대충 제출해보다 WA가 나와서 좀 더 생각하게 되었다.

그냥 문자열은 다 갖다 버리자.

첫 예시는 ?:?: 이고 두 번째는 ??:: 이다.

항상 어떠한 ?: 는 하나의 괄호로 묶을 수 있다.

모두 ?:?:?:?:... 라고 가정해보자.

그런데 ?: 를 괄호로 묶은 다음에는 항상 인접한 ?: 와 합쳐줄 수 있다. 그럼 정확히 항이 하나 줄어들고, 이 때 왼쪽에서 오른쪽으로 합칠지, 반대일지에 따라 $2$가지 경우로 나뉜다.

즉, 카탈란 수의 정의와 동일하다.

카탈란 수의 정의는 $n$ 개의 인수의 곱을 결합법칙이 성립하지 않을 때 표현하는 경우의 수이기 때문이다.

카탈란 수의 점화식 꼴은 다음과 같다.

$C(n)=\displaystyle \sum_{i=0}^{n-1}C(i) \cdot C(n-1-i)=\dfrac{1}{n+1}\dbinom{2n}{n}$

따라서 $O(n)$ 에 전처리하면 구할 수 있다.

Solution

항상 모든 경우가 ?:?:?: 가 되지 않는다.

? 를 ( 로, : 를 ) 로 나타낸 괄호 문자열(RBS)을 고려한다.

현재 RBS의 balance value가 $k$ 일 때, 자신 위에있는 $k+1$ 높이의 RBS 묶음의 개수만큼 카탈란 수를 정답에 곱해줘야 한다.

예를 들어, 아래 그림에서 수평선에선 $3$개 의 봉우리가 있으므로 $C(3)$ 을 정답에 곱해준다.

왜냐면 저 $3$개의 봉우리는 각각 지들끼리 안에서 합쳐진다음 거대한 삼항연산자의 항이 되었기 때문이다.

따라서 그 거대한 삼항연산자 묶음 $3$개를 다시 카탈란수의 경우의 수로 배치할 수 있는 경우의 수를 정답에 곱해주는 것이다.