1328번 : 고층 빌딩 [C++]

문제 풀이

성공 여부(걸린 시간): 대실패(1시간)

아이디어

실패접근법

처음에 점화식을 작성하는데 머리가 터지는 줄 알았다.

가장 큰 빌딩을 기준으로 좌 우를 나누는 것을 생각하고 조합을 이용해서
1시간 동안 완벽한 점화식을 짜려고 노력했으나 실패하고 지피티에게 물어봤다.

 

점화식

// 추가하는 건물 i, 왼쪽에서 보이는 건물 j, 오른쪽 k
// 현재 = 오른쪽 추가 (왼쪽 +1) + 왼쪽 추가 (오른쪽 +1) + 중간 *(중간에 놓을 수 있는 경우의 수)
dp[i][j][k] = (dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] + (long long)dp[i - 1][j][k] * (i - 2))%mod;

 

풀어서 설명하자면

그림판으로 그린 이 그림을 요약하자면

세가지의 전 단계의 결과를 다음 결과에 반영하게 되는데

1. 제일 오른쪽에 건물 추가한 경우

2. 제일 오른쪽에 건물 추가한 경우

3. 사이에 넣은 경우 * 사이에 넣을 수 있는 경우의 수  (int타입으로 하면 오버플로우남)

 

그렇게 해주고 마지막에 출력해주면 끝.

풀이 코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, L, R;
    int mod = 1000000007;
    cin >> N >> L >> R;
    int dp[101][101][101];
    dp[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++) {
                // 추가하는 건물 i, 왼쪽에서 보이는 건물 j, 오른쪽 k
                // 현재 = 오른쪽 추가 (왼쪽 +1) + 왼쪽 추가 (오른쪽 +1) + 중간 *(중간에 놓을 수 있는 경우의 수)
                dp[i][j][k] = (dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] + (long long)dp[i - 1][j][k] * (i - 2))%mod;
            }
        }
    }
    cout << dp[N][L][R];
    return 0;
}