[Python] 21739번 펭귄 네비게이터

 

https://www.acmicpc.net/problem/21739

21739번: 펭귄 네비게이터

---

 

23/12/06

 

 

이것도 카탈란 수임을 알면 매우 쉬운 문제이다.

---

 

문제 접근 방식:

 

 

이 문제는 카탈란 수 임을 알아내는게 조금 까다롭다.

 

영 타블로를 잘 알고 있는 사람이라면 이 그림이 $2 \times n$짜리 영 타블로의 개수이고, 이를 계산하면 카탈란 수라는 사실을 알 수 있다.

 

근데 이건 좀 더 나아간 설명이고, 그림을 살펴보면, "항상" 윗 줄보다 밑 줄의 원소가 더 크다는 사실을 확인할 수 있다.

 

격자 경로에서 대각선 부분을 넘어갈 수 없다는 제약이 걸린 것과 비슷하지 않은가?

 

실제로, 격자 경로에서 대각선 부분을 넘어갈 수 없다는 제약이 걸리면, 이 경로의 개수는 카탈란 수와 같다는 사실은 널리 알려진 사실이다.

 

따라서 이 그림과 저 격자 경로를 일대일 대응 시킬 수 있다는 사실만 확인하면, 카탈란 수임을 확인할 수 있다.

 

$2n$개의 숫자가 그림에 나타난다.

 

우리는 격자 경로를 $2n$의 길이로 구성할 건데, 위로 올라가는 경로는 $U$로, 오른쪽으로 가는 경로는 $R$로 표현할 것이다.

 

그리고, 그림 밑 줄에 나타나있는 숫자를 인덱스로 하여, 그 인덱스엔 $U$로 하고 그게 아니라면 오른쪽으로 가도록 경로를 구성하면 된다.

 

예를 들어, 그림이 다음과 같이 주어져 있다고 하자.

$$\begin{matrix} 1 & 2 & 5 \\ 3 & 4 & 6 \\ \end{matrix}$$

그러면, 이를 $RRUURU$로 표현할 수 있고, 이를 격자 경로로 표현하면 다음 그림과 같다.

 

이렇게 격자 경로를 구성하면 일대일 대응이 잘 만들어 지므로, 우리는 두 대상이 서로 개수가 같음을 확인할 수 있다.

 

파이썬의 경우 시간초과가 날 수 있기 때문에 팩토리얼의 인버스값을 전처리하여 카탈란 수의 일반항을 통해 구하면 빠르게 구할 수 있다.

 

Reference : https://math.stackexchange.com/questions/2531867/the-number-of-the-shape-of-2-times-n-young-tableaux-is-catalan-number

The number of the shape of $2 \times n$ Young Tableaux is Catalan number

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 21739번 펭귄 네비게이터
# DP, 조합론
'''
접근 방법:
카탈란 수
'''
import sys
input = sys.stdin.readline

MOD = 1_000_000_000+7
fac = [-1 for _ in range(30_001)]
fac_inv = [-1 for _ in range(30_001)]
fac[0] = 1
for i in range(1, 30_000+1):
    fac[i] = (fac[i-1]*i)%MOD
fac_inv[30_000] = pow(fac[30_000], MOD-2, MOD)
for i in range(30_000, 0, -1):
    fac_inv[i-1] = (i*fac_inv[i])%MOD
def comb(n, r):
    if n < r:
        return 0
    return (((fac[n]*fac_inv[r])%MOD)*fac_inv[n-r])%MOD
def modInverse(a, m): # m이 소수인 경우
    return pow(a, m-2, m)
def Catalan(n):
    return (comb(2*n, n)*modInverse(n+1, MOD))%MOD
N = int(input())
print(Catalan(N))