백준 1328번 고층 빌딩

문제 링크입니다: https://www.acmicpc.net/problem/1328

3가지 경우의 수를 고려해야합니다.

1. N-1 높이의 빌딩을 좌측과 우측을 제외한 곳에 추가하면 L과 R은 그대로입니다.

2. N-1 높이의 빌딩을 좌측에 추가하면 L은 하나 증가합니다.

3. N-1 높이의 빌딩을 우측에 추가하면 R은 하나 증가합니다.

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const long long MOD = 1000000007;

const int MAX = 100 + 1; //1<=N<=100

 

int N, L, R;

long long cache[MAX][MAX][MAX];

 

long long numOfWays(int buildingNum, int left, int right)

{

        //기저 사례: 오름차순, 내림차순

        if ((left == 1 && right == buildingNum) || (left == buildingNum && right == 1))

                 return 1;

        //불가능한 경우

        if (buildingNum == 0 || left == 0 || right == 0)

                 return 0;

 

        long long &result = cache[buildingNum][left][right];

        if (result != -1)

                 return result;

 

        result = 0;

        //1. 좌측과 우측을 제외한 곳에 추가하면 그대로

        //2. N-1 높이를 가진 건물을 우측에 추가하면 우측에서 보이는 건물 증가

        //3. N-1 높이를 가진 건물을 좌측에 추가하면 좌측에서 보이는 건물 증가

        result = ((numOfWays(buildingNum - 1, left, right) * (buildingNum - 2)) + numOfWays(buildingNum - 1, left - 1, right) + numOfWays(buildingNum - 1, left, right - 1)) % MOD;

 

        return result;

}

 

int main(void)

{

        cin >> N >> L >> R;

       

        memset(cache, -1, sizeof(cache));

 

        cout << numOfWays(N, L, R) % MOD << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~