BOJ 8895(막대 배치) 풀이

solved.ac 티어 : 골드 2

www.acmicpc.net/problem/8895

8895번: 막대 배치

 

이문제는 dp이다. 

점화식은 dp[n-1][l-1][r]+dp[n-1][l][r-1]+(i-2)*dp[n-1][l][r]이다.

dp[n-1][l-1][r]는 재일 왼쪽 막대를 뺐을 때이고

dp[n-1][l][r-1]는 재일 오른쪽 막대를 뺐을 때이고

dp[n-1][l][r]*(i-2)는 양쪽 막대를 제외한 나머지 막대를 배치할 수 있는 경우의 수이다.

 

import sys
input=sys.stdin.readline
dp=[[[0 for i in range(23)]for g in range(23)]for q in range(23)]
dp[1][1][1]=1
for i in range(2,21):
    for g in range(1,21):
        for q in range(1,21):
            dp[i][g][q]=dp[i-1][g-1][q]+dp[i-1][g][q-1]+(i-2)*dp[i-1][g][q]
a=int(input())
for _ in range(a):
    n,l,r=map(int,input().split());print(dp[n][l][r])