[프로그래머스,Java] Level4 : 쌍둥이 빌딩 숲

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

프로그래머스

문제분석:

 

 

n쌍의 쌍둥이 빌딩이 그림과같은 규칙으로 서있을때, 

은비가 바라봣을때 보이는 모습이 몇가지가 존재하는지 반환하는 모습이다.

 

 

즉, 은비가 그림과같이 바라보는 모습은 서로다른 쌍이 2개이니, 

서로다른 2개의 건물이 겹쳐보이는 n쌍의 빌딩의 경우의수를 구하면된다.

 

일단 계산값을 100,000,007로 나눠달라는것과 규칙성의 냄새가나면  점화식 DP다.

 

일반 구현으로 해결할수있는 DP는 조금 쉽지만 (구현,다익스트라, 플로이드와샬) 

 

이런 점화식을 통한 DP는 규칙찾기가 매우매우 힘들다.

 

입출력에서 보면 숨겨진 힌트가있다.   n과 count별로 값이 정리되어있다.

 

즉, dp는  2차원배열로    [쌍둥이빌딩 쌍 갯수] [Count]로 작성하라는 숨겨진?의미다.

 

 

이제 규칙성을 찾아봐야한다.

 

우선 dp[2][1]  : 쌍둥이 2개쌍에 count 1인 경우

 

dp[1][?] 에서 어떤규칙을 통해  dp[2][1]로 만들어지는지 유추해야한다.

유추할때도 2가지가 있다.  dp[1]에서 지금까지 나온 빌딩보다 높은 건물을 짓는걸 가정할지, 또는 낮은 건물을 짓는걸 가정할지이다.

 

가장 낮은건물을 짓는걸로 가정하는게 더욱 접근하기 쉽다.

 

그이유는, 가장 높은 건물을 짓는걸로 가정하면,  Count가 2,3,4,5,6,7,...이여도, 건물이 맨앞에오면 Count 1로 퉁쳐버리기때문에  고려해야할게 많아진다.

 

dp[2][1]  count1로 만들어지는 경우를  가장 낮은건물로 짓는걸로 가정해본다. 

여기까지 생각이 도달했다면  그나마 조.금..? 쉬워진다.

 

dp[1][1] ->  dp[2][1]로 변환하는 경우를 생각해보자.

이 경우는, 은비가 본 경치가 변환이 없는경우므로,  이미 세워진 건물 뒤에 숨겨 지어진경우다.

=> EX)   11  =>  1x1  ,  11x   

dp[2][1] -> dp[3][1]로 만들어지는 경우도 생각해보자.

=> EX)  2112 => 2x112, 21x12, 211x2, 2112x   이다. 

 

보아하니, 맨 앞을 제외해서 사이사이, 끝부분에 놓으면 된다. 그 자릿수는  현재 쌍의갯수가 n이면, (n-1)*2 갯수다.

 

즉,  (n-1)*2* 이전DP이다. 

 

그리고 또 한가지 더 생각해야한다.  맨앞을 제외한 저 경우도 고려해야한다.

가장작은 맨 앞의 건물이 생성되면 Count가 1이 증가한다.

 

즉,  dp[2][1]이면  dp[1][0]에서 변환하는것이다.

 

즉,  1(맨앞)*dp[1][0]이다. 

 

정리하자면...   dp[n][count] 를 구하자고하자면,

 

dp[n][count] =  (n-1)*2*dp[n-1][count] + dp[n-1][count-1]

 

 

전체풀이 

 

class Solution {
    public int solution(int n, int count) {
        int answer = 0;
       
        // dp[n][count] 의 이중 dp 생성
         
        int[][] dp = new int[n+1][n+1]; 
     
        dp[1][1]=1;
        
        // 가장 큰 건물부터 세워졋다고 가정함
        // dp[2][1] 이 생성되는경우
        // dp[1][1] 에서 안보이게 넣는경우 -> (n-1)*2*dp[1][1] 갯수
        // dp[1][0] 에서 보이게 넣는경우 -> dp[1][0] => 없음
        
        // dp[2][2]가 생성되는경우
        // dp[1][2] 인경우는 존재하지가 않음 => 0개
        // dp[1][1]에서 보이게 넣으므로, 맨앞에 생성 => 1*dp[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 answer;
    }
}