[ALGORITHM] LEVEL4 - 쌍둥이 빌딩 숲

https://school.programmers.co.kr/learn/courses/30/lessons/140105

프로그래머스

생각의 흐름

1. 빌딩의 각 크기별 갯수는 2개 이며, 작은 빌딩 사이에 큰 빌딩은 들어가지 못한다.
2. 그러면 작은 순이 아닌 큰 빌딩 순으로 넣는다면?
3. 작은 빌딩을 먼저 놓는 경우 이후에 놓을 빌딩이 무조건 보이므로 계산이 햇갈릴 것 같아 역순으로 진행
4. 보이는 경우와 안보이는 경우로 나눠서 진행
5. DP[현재 빌딩 높이][보이는 빌딩의 갯수]
6. DP[현재][갯수] = DP[현재+1(이전)][갯수] + DP[현재+1][갯수-1]
7. DP[현재+1][갯수-1]의 경우 현재 높이의 빌딩이 무조건 보여야 하므로 맨 앞에 위치하게 됨.
8. DP[현재+1][갯수]의 경우 빌딩의 갯수가 (idx-1) *2 (idx는 역순의 인덱스) 개가 존재하게 된다. (현재 빌딩은 아직 안놓였으므로)
   • ex) 4개가 있을때 4,3 을 구하는 경우 현재 놓아야 하는 빌딩의 높이가 1이면 2,3,4의 빌딩은 이미 놓여있는 것이므로 (idx-1)*2 = 3*2 가 된다. idx는 현재 놓아야 할 빌딩의 index이므로 4번째가 되어 idx=4
9. idx의 경우 역순 연산으로 따로 계산식을 세워야 하여 단순하게 하기 위해 변수로 지정

예제

4 1 48
4 3 12

 

코드

#include <string>
#include <vector>

using namespace std;

//조합 빌딩 높이의 내림차순으로 세운다면
//100^2 dp로 가능?
//빌딩 높이 / 현재 까지 보이는 빌딩 갯수
// 4 3
// 1 2 4 2
// 1 3 4 4
// 2 3 4 6
long long dp[101][101];
int mod = 1'000'000'007;

int solution(int n, int count) {
    int answer = 0;
    
    dp[n][1]=1;
    for(int i=n-1, idx=2;i>0;--i, ++idx){
        for(int j=idx;j>=1;--j){
            dp[i][j] = (dp[i+1][j] * (idx-1)*2 + dp[i+1][j-1]) % mod;
        }
    }
    
    answer = dp[1][count];
    return answer;
}