티스토리 뷰
https://www.acmicpc.net/problem/1328
1328번: 고층 빌딩
상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다. 상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다. 빌딩의 개수 N과 가장 왼쪽에서
www.acmicpc.net
D[N][L][R] = 각각 1~N의 높이를 가진 빌딩을 세웠을 때 가장 왼쪽에서 L개, 가장 오른쪽에서 R개의 빌딩이 보이는 경우의 수
D[N][L][R] = D[N-1][L-1][R] + D[N-1][L][R-1] + D[N-1][L][R]*(N-2)
1~N-1의 높이를 가진 빌딩의 경우의 수에서 높이를 1씩 높여주면 2~N의 높이를 가진 빌딩의 경우의 수가 나온다.
2~N의 높이를 가진 빌딩에서 1를 가장 왼쪽에 추가, 가장 오른쪽에 추가, 그 외 사이에 추가하는 경우의 수를 합한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <cstdio>
long long n,l,r,i,j,k,d[105][105][105];
int main()
{
scanf("%lld %lld %lld",&n,&l,&r);
d[1][1][1]=1;
for(i=2;i<=n;i++)
{
for(j=1;j<=l;j++)
{
for(k=1;k<=r;k++)
{
d[i][j][k]=d[i-1][j-1][k]+d[i-1][j][k-1]+d[i-1][j][k]*(i-2);
d[i][j][k]%=1000000007;
}
}
}
printf("%lld",d[n][l][r]);
return 0;
}
|
cs |
'Algorithm > BOJ' 카테고리의 다른 글
| 2133 타일 채우기 (0) | 2019.10.13 |
|---|---|
| 12969 ABC (0) | 2019.10.13 |
| 10942 팰린드롬? (0) | 2019.10.12 |
| 1890 점프 (0) | 2019.10.12 |
| 11048 이동하기 (0) | 2019.10.12 |