프로그래머스 쌍둥이 빌딩 숲 (C#) [Lv. 4]

프로그래머스

높이가 1 ~ n까지인 빌딩이 2개씩 존재할 때, 은비가 바라본 방향에서는 count개의 빌딩이 보인다고 합니다. 이 때, 빌딩들이 배치될 수 있는 방법의 수를 구해주세요. (같은 높이를 가진 빌딩 사이에는 그보다 높은 빌딩이 없습니다.)

 

 

풀이 방법

점화식을 찾고 풀이하는 동적 프로그래밍을 통해 해결해야합니다. 

DP[i, j] -  높이가 1부터 i까지 각각 2개씩 있는 빌딩을 배치할 때, j개의 빌딩이 보이는 경우의 수.

 

점화식은 두 가지 경우로 나뉩니다.

1. 기존에 보이는 빌딩의 개수를 유지하는 경우 

 (dp[i-1, j] * (i-1) * 2):

• 높이가 i인 빌딩을 배치하더라도, 보이는 빌딩의 개수(j)가 변하지 않습니다.
• 높이가 i인 빌딩은 기존 배치에 추가될 때, 기존의 빌딩들 사이에 배치됩니다.
• 높이가 i인 빌딩은 기존 배치에서 (i-1) * 2개의 위치에 배치될 수 있습니다.
  • (i-1): 높이가 i-1까지의 빌딩들이 이미 배치되어 있으므로, 그 사이에 배치할 수 있는 위치의 수.
  • * 2: 높이가 i인 빌딩이 2개이므로, 각 위치에 2개의 빌딩을 배치할 수 있습니다.

 

2. 새로운 빌딩이 보이도록 하는 경우

 (dp[i-1, j-1]):

• 높이가 i인 빌딩을 배치할 때, 새로운 빌딩이 보이도록 합니다.
• 이 경우, 보이는 빌딩의 개수(j)가 1 증가합니다.
• 높이가 i인 빌딩은 가장 오른쪽에 배치되어야 합니다. 이렇게 해야 새로운 빌딩이 보이게 됩니다.

 

예시: n = 3, count = 2
dp[1, 1] = 1: 높이가 1인 빌딩 2개를 배치할 때, 1개의 빌딩이 보이는 경우의 수는 1입니다.

dp[2, 1] = dp[1, 1] * 1 * 2 + dp[1, 0] = 1 * 2 + 0 = 2
높이가 2인 빌딩을 배치하더라도 보이는 빌딩의 개수가 유지되는 경우: 2가지.

dp[2, 2] = dp[1, 2] * 1 * 2 + dp[1, 1] = 0 * 2 + 1 = 1
높이가 2인 빌딩을 배치하여 새로운 빌딩이 보이도록 하는 경우: 1가지.

dp[3, 1] = dp[2, 1] * 2 * 2 + dp[2, 0] = 2 * 4 + 0 = 8
높이가 3인 빌딩을 배치하더라도 보이는 빌딩의 개수가 유지되는 경우: 8가지.

dp[3, 2] = dp[2, 2] * 2 * 2 + dp[2, 1] = 1 * 4 + 2 = 6
높이가 3인 빌딩을 배치하여 새로운 빌딩이 보이도록 하는 경우: 6가지.

dp[3, 3] = dp[2, 3] * 2 * 2 + dp[2, 2] = 0 * 4 + 1 = 1
높이가 3인 빌딩을 배치하여 새로운 빌딩이 보이도록 하는 경우: 1가지.

 

 

정답 코드

using System;

public class Solution {
    public int solution(int n, int count) {
        long answer = 0;
        long[,] dp = new long[n+1,n+1]; // dp[n, count]
        dp[1,1] = 1;
        
        for(int i= 2; i <= n; i++)
        {          
            for(int j = 1; j <= i; j++)
            {              
                dp[i,j] = (dp[i-1,j] * (i-1) * 2 + dp[i-1,j-1]) % 1000000007;
            }
        }
        
        answer = dp[n, count];
        
        return (int)answer;
    }
}