[Python] 4811번 알약

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

4811번: 알약

---

 

23/07/05

 

 

카탈란 수임을 알면 쉽게 풀 수 있고, 그게 아니더라도 2차원 DP로 쉽게 해결할 수 있다.

---

 

문제 접근 방식:

 

 

반 조각을 꺼내는 행동은 이전에 한 조각을 꺼내는 행동이 수반되었어야만 나올 수 있다.

 

따라서 이건 카탈란 수열임을 확인할 수 있다.

 

한편, 그냥 2차원 DP로도 접근할 수 있다.

 

$DP[i][j]$ = 현재 $i$일이고, 반조각을 꺼낼 수 있는 횟수가 $j$번일 때의 문자열 개수

 

라고 정의하자.

 

그러면 점화식은 $DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]$로 나옴을 알 수 있다.

 

왜냐하면, 현재 날짜에서 반조각을 꺼냈거나 한조각을 꺼냈거나 둘 중 하나이기 때문에, 반조각을 꺼냈다면 $DP[i-1][j+1]$, 한 조각을 꺼냈다면 $DP[i-1][j-1]$이 되기 때문이다.

 

---

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

# 4811번 알약
# DP
'''
접근 방법:
DP[i][j] = 현재 i일이고, 반조각을 꺼낼 수 있는 횟수가 j번일때의 문자열
DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]
DP[i][0] = DP[i-1][1]
DP[i][30] = DP[i-1][29]
DP[1][0] = 1
'''
import sys
input = sys.stdin.readline

DP = [[0 for _ in range(31)] for _ in range(61)]
DP[1][0] = 1
for i in range(2, 61):
    DP[i][0] = DP[i-1][1]
    for j in range(1, 30):
        DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]
    DP[i][30] = DP[i-1][29]
    
while True:
    n = int(input())
    if n == 0:
        break
    print(DP[2*n][1])