[프로그래머스/C++] 쌍둥이 빌딩 숲

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 DP를 이용하면 빠르게 풀 수 있는 문제다.

 

처음에는 큰 빌딩이 새로 생긴다고 생각하고 새로 추가된 큰 빌딩을 기준으로 삼 combination을 이용해 문제를 풀려고 했다.

이렇게 문제를 풀자 문제가 풀리긴 풀리는데 수가 너무 커 1000000007로 나누어 줘야하고, 곱셈을 하는 과정에서 범위를 넘어가기도 했다. 그래서 반대로 작은 빌딩이 추가가 된다고 생각하고 문제를 풀었다.

 

예를 들어 앞에서 봤을 때 count가 1이고 빌딩의 수가 2인 경우에서, 빌딩의 수가 3으로 늘어난다고 생각을 하자

(2, 1) => 빌딩의 수가 2이면서 count가 1인 경우의 수

그러면 작은 빌딩사이에 큰 빌딩이 들어오지 못하므로 작은 빌딩은 붙어있어야 한다.

그래서 그림에서 보이는 것과 같이 작은 빌딩을 주가할 수 있는 부분은 4곳으로 (2,1) * 4의 경우의 수가 추가된다.

 

여기서 주의할 점은 (2, 1)의 경우는 경우의 수가 1가지가 아니라는 점이다.

(2, 1)을 만족하는 그림은 아래와 같은 경우도 존재한다.

그러므로 (3, 1)을 만족하는 경우의 수는 8이다.

 

 

이번에는 조금 다른 경우를 생각해보자

 

앞에서 봤을 때 count가 2이면서, 빌딩의 수가 3인 경우다.

그림에서 알 수 있듯이 (2,1)의 경우에는 무조건 앞에 두어야하고 (2,2)의 경우에는 마찬가지로 4곳에 둘 수 있다.

 

그러므로 (2, 1)*1+(2,2)*4가 (3,2)의 정답이 된다.

 

이를 이용하면 S(n, count) = S(n-1,count-1) + S(n-1,count)*(n-1)*2 와 같이 점화식을 나타낼 수 있다.

 

[아이디어 정리]

1. 빌딩의 수가 늘어날 때마다 작은 빌딩이 추가된다고 생각한다.
2. 작은 빌딩이 추가가 될 경우 작은 빌딩을 어느 위치에 놓을 수 있는지 개수를 세고, 추가되기 전 경우의 수에 곱해 더한다.
3. 점화식을 통해 구한 값을 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;
const int a = 1000000007;
vector<vector<long long>>DP;
long long Calc(int b, int c)
{
    if (DP[b][c]!=0)
    {
        return DP[b][c];
    }
    if(b-1>0&&c>0)
    {
        DP[b][c]+=Calc(b-1,c)*((b-1)*2);
    }
    if (b-1>0&&c-1>0)
    {
        DP[b][c]+=Calc(b-1,c-1);
    }
    DP[b][c]%=a;
    return DP[b][c];
}
int solution(int n, int count) {
    DP = vector<vector<long long>>(n+1,vector<long long>(n+1,0)); // [a][b] a개의 블럭으로 b개의 모습을 나타내는 방법의 수
    for (int i=1; i<n+1; i++)
    {
        DP[i][i]=1;
    }
    return Calc(n,count);
}

 

---

 

처음에 큰 빌딩으로 문제를 풀면서 조합을 이용해 계산을 했었는데, 자꾸 실패가 떴다.

정말 왜 답이 틀리는지 아무리 고민해도 모르겠어서, 작은 빌딩으로 풀고 경우의 수를 비교했다.

그랬더니 일정 범위까지는 똑같이 수를 뽑아내는데, 어느 범위를 넘어가면 값이 달라지기 시작하면서 같은 값이 계속 출력됐다.

아무래도 조합으로 구하는 경우 곱셈연산을 하는 과정에서 long long 범위를 넘어가게 돼 값이 중간에 이상이 생겼던 것 같다... 내 시간.... ㅠㅠㅠ

 

 

프로그래머스