728x90
1328번: 고층 빌딩
상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼
www.acmicpc.net
분석
- D[N][L][R] : N개의 빌딩이 있고 왼쪽에서 볼 때 L개, 오른쪽에서 볼 때 R개가 가능한 경우의 수
- 가장 작은 빌딩을 N번째로 배치한다고 가정
- 가장 앞에 배치 : D[N][L][R] = D[N-1][L-1][R] ← 왼쪽에서 보이는 갯수가 +1
- 가장 뒤에 배치 : D[N][L][R] = D[N-1][L][R-1] ← 왼쪽에서 보이는 갯수가 +1
- 가운데에 배치 : D[N][L][R] = D[N-1][L][R] * (N-2) ← 보이는 갯수 동일, 가운데 배치 할 경우의 수(N-2개의 위치)
풀이
import sys
input=sys.stdin.readline
n,l,r=map(int, input().split())
d=[[[0 for k in range(101)] for j in range(101)] for i in range(101)]
d[1][1][1] = 1 # 빌딩이 1개인 경우
for i in range(2, n+1): # 빌딩의 개수
for j in range(1, l+1): # 왼쪽에서 볼 때
for k in range(1, r+1): # 오른쪽에서 볼 때
# 제일 작은 건물
# 왼쪽에 놓는 경우의 수(왼쪽에서 보이는거 +1)
# + 오른쪽에 놓는 경우의 수(오른쪽에서 보이는거 +1)
# + 가운데 놓는 경우의 수
d[i][j][k]= d[i-1][j-1][k] + d[i-1][j][k-1] + d[i-1][j][k]*(i-2)
print(d[n][l][r]%1000000007)
728x90