[Python] 4099번 Skyline

 

 

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

4099번: Skyline

---

 

23/12/06

 

 

카탈란 수 임을 파악하면 쉽게 해결할 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

먼저 문제의 입출력 예시를 보자.

 

어? $3$일때 $5$가 나오고 $4$일때 $14$가 나오네? 이거 카탈란 수인가? 하고 문제를 유추한 다음, 실제로 카탈란 수를 구현하면 맞았습니다를 받을 수 있다.

 

그러면 이제 왜 이 문제의 점화식이 왜 카탈란 수가 나오는지 생각해보자.

 

$N$번째 상황이라고 생각해보자. 또한, 건물의 높이를 나타내는 배열은 $S$라고 해보자.

 

문제의 요점은 $i < j < k$이면서 $S[i] < S[j] < S[k]$가 되지 않도록 하는 경우의 수를 구하는 것이다.

 

$N$번째 상황이라고 가정했으니, 가장 높은 건물의 높이는 $N$일 것이다.

 

가장 높은 건물이 어디 있냐를 잘 생각해보자.

 

가장 높은 건물은 사실 어디 있든 간에, $i < j < k$이면서 $S[i] < S[j] < S[k]$에서 $j$역할을 담당할 수 없다.

 

왜냐하면 가장 높기 때문이다.

 

따라서 우리는 가장 높은 건물을 기준으로 왼쪽과 오른쪽으로 "분리"할 수 있다.

 

$N$번째 경우의 수를 $C_N$이라고 하고, 가장 높은 건물이 위치한 인덱스를 $i$번째 인덱스라고 하면, 가장 높은 건물을 기준으로 왼쪽과 오른쪽으로 분리할 수 있으므로, $C_{i-1} * C_{N-i}$로 경우의 수를 나타낼 수 있다.

 

가장 높은 건물이 위치한 곳은 첫번째부터 $N$번째 까지 가능하므로, 이를 모두 합산하면 카탈란 수의 점화식이 나온다.

 

따라서 이를 그대로 구현하면 끝이다. 

---

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

# 4099번 Skyline
# DP, 조합론
'''
접근 방법:
카탈란 수
'''
import sys
input = sys.stdin.readline

MOD = 1_000_000
Catalan = [0 for _ in range(1001)]
Catalan[0], Catalan[1] = 1, 1
for i in range(2, 1001):
    C = 0
    for j in range(i):
        C += (Catalan[j]*Catalan[i-j-1])%MOD
    C %= MOD
    Catalan[i] = C
while True:
    N = int(input())
    if N == 0:
        break
    print(Catalan[N])