[백준] 1328번 고층 빌딩(c++)
[백준] 1328번 고층 빌딩
문제 링크: https://www.acmicpc.net/problem/1328
문제 및 입출력
문제 접근
도저히 생각이 나지 않아 다른 사람의 블로그를 참고를 하였다.
이전의 빌딩 갯수에서 빌딩의 높이를 하나씩 높인다고 가정한다. 그 후에, 높이가 1인 빌딩을 놓을 곳을 찾으면 된다. 가장 좌측에 놓는 경우와 가장 우측에 놓는 경우는 각각 왼쪽에서 보이는 경우, 오른쪽에서 보이는 경우가 1씩 추가된다.
양 끝이 아닌 부분들은 보이는 갯수에 대한 변화는 없기 때문에 놓을 수 있는 위치는 i-2이다.
점화식: dp[i][j][k] = cache[i-1][j-1][k] + cache[i][j][k-1] + cache[i-1][j][k] * (i-2)
코드 구현(c++)
#include<iostream>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
ll cache[102][102][102];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int N, L, R;
cin >> N >> L >> R;
cache[1][1][1] = 1;
for(int i = 2 ; i <= N ; i++){
for(int j = 1 ; j <= L ; j++){
for(int k = 1 ; k <= R ; k++){
cache[i][j][k] = (cache[i-1][j-1][k] + cache[i-1][j][k-1] + cache[i-1][j][k] * (i-2)) % mod;
}
}
}
cout << cache[N][L][R] << "\n";
}
Author And Source
이 문제에 관하여([백준] 1328번 고층 빌딩(c++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kpg0518/백준-1328번-고층-빌딩c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)