쌍둥이 빌딩 숲 (Java)

접근 방법

1. (패턴) n개의 빌딩을 높은 순서대로 문제에 나온 룰을 지키면서 배치를 해본다고 가정을 한다.
   • 첫 빌딩은 연달아서 두개를 놓는 방법 외에는 다른 수가 없기 때문에 경우의 수는 1이 될 수 밖에 없다.
   • 다음 빌딩을 놓을 때는 우리 두 가지의 가능성을 생각할 수 있다. 첫 번째는 원래 있는 배치도에서 제일 앞단에 배치를 해서 은비가 보는 빌딩의 가짓수를 1 만큼 늘리는 것이고, 아니라면 맨 앞에 두지 않도록 배치해서 가짓수를 그대로 두는 방식이다.
   • 다시 다른 빌딩을 놓을 때도 다시 두 가지 방식을 생각할 수 있다. 맨 앞에 놓거나(= 가짓수 늘리기), 아니면 그렇지 않게 배치할 수 있다.
   • 마지막 빌딩까지 반복된다.
2. (DP) 그렇다면 위처럼 배치하면서 k번째 단계에서 count만큼 보이도록 배치하려면 어떻게 해야할까? 먼저, k 번째 단계에서 배치하는 빌딩은 가장 짧은 빌딩일 것이다. 그렇다면,
   • k - 1개의 빌딩을 배치했는데 count - 1개의 빌딩이 보이면, 제일 앞에 배치하면 보이는 가짓수가 count개 만큼 된다 : dp[k - 1][count - 1] 만큼의 가짓수가 존재
   • k - 1개의 빌딩을 배치했는데 count개의 빌딩이 보이면, 처음 보이는 빌딩이 뭐든 그 빌딩 뒤에 어디든지만 배치하면 된다. 이 때 k 번째 빌딩이 들어갈 수 있는 가짓수는 2 X (k - 1)개 만큼 있을 것이고 (빌딩은 두 개가 세트), 그 가짓수에 배치하기 전에 count개의 빌딩이 보이는 가짓수를 곱하면 된다 : 2 X (k - 1) X dp[k - 1][count] 만큼의 가짓수가 존재
   • 위의 두 케이스를 더하면 k번째 단계에서 count만큼 보이는 경우의 수가 된다.
3. (최적화) 우리가 관심있는 경우의 수는 count까지이다. 따라서 count까지의 DP 값만 보관해도 무방하다.

코드

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

배운 점

1. 보통 테스트케이스에 문제를 접근하는 방법에 대한 힌트를 주는 경우가 많은 것 같다. 테스트케이스의 규칙을 찾아서 해결해보자.
2. DP 문제인 것 같다면 점화식을 세울 때 DP를 재료로 사용해서 다시 후처리를 하는 것이 아닌, 각 stage가 바로 정답이 될 수 있도록 설계를 하자.

참고

https://dev-skill.tistory.com/128

[Java] 프로그래머스 [Level-4] 쌍둥이 빌딩 숲