[Unsolved][C++] 백준 1010 다리 놓기

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

1. 서론

 

문제 자체는 되게 심플하다. 조합론을 통해 그 결과 값도 아니고 그게 몇 번 반복되는지 구하는 문제. 근데... 함정이 있었다.

 

2. 문제 풀이

 

강 서쪽에 다리를 지을 수 있는 곳 N 개, 강 동쪽에 다리를 지을 수 있는 곳 M개가 있다. M은 항상 N과 같거나 크다. 이 중 양쪽을 연결해서 다리를 지을 수 있는 경우의 수를 구하는 것이다.

 

근데... 문제는 여기서 난 처음에 이걸 순열이라고 생각했다는 것이다. 왜냐면 예를 들어 강 서쪽에서 1번, 강 동쪽에서 4번을 고르는 거랑 5번을 고르는 거랑 다르니까... 순서가 상관있는 것 같아 => 순열... 이랬다는 것이다. 근데 (1, 4)와 (1, 5)는 순서가 문제가 아니라 그냥 조합이 다른 거잖아... 어차피 양쪽의 스폿은 N, M으로 정해져 있으니까 순열이 아니라 조합이다. 즉, (1, 4)나 (4, 1)은 같으니까 상관없다.

이게 나의 첫 번째 고비였다.

 

가까스로 고비를 넘긴 나는... 조합으로 문제를 풀었다. 그런데 보통 조합은 재귀로 많이 푸는데 테케의 1,2는 되도 3이 안 되는 것이다. 바로 '시간 초과' 때문에! 그렇다. 재귀를 너무 많이 해서 시간 복잡도가 터진 것이다. 그래서 인터넷을 찾아보니 DP를 활용해서 풀란다. 하,,, 난 조합 코드 익힐라고 이 문제 골라서 풀었는데 DP까지 하란다. 하지만 DP를 사용하게 되면 지금 썼던 코드는 아예 쓸 수 없어 새로 짜야했다. 그리고 난 학교 다닐 때 이미 DP GG 선언을 한 사람이라... 그냥 조합 DP 구현이라고 인터넷에 검색하게 되었다.

 

https://bghgu.tistory.com/18

조합 DP 알고리즘

 

그리고 이 블로그를 참조해서 풀게 되었다. (알고리즘 공부할라고 맨날 문제 푸는데 검색만 오지게 하고 스스로 되지는 않네 ㅎㅎ)

 

3. 코드 설명

 

#include <cstring>
#include <iostream>

using namespace std;

int dp[30][30];

int c(int n, int r)
{
    if (dp[n][r] != 0) return dp[n][r];
    if (n == r || r == 0) return 1;

    dp[n][r] = c(n - 1, r - 1) + c(n - 1, r);
    return dp[n][r];
}

int main()
{
    int t, n, m, i;
    
    cin >> t;
 
    for (i = 0; i < t; i++)
    {
        cin >> n >> m;

        cout << c(m, n) << endl;
        memset(dp, 0, sizeof(dp));
    }
}

 

c 배열에서 조합을 DP로 구현해준다.

우리가 수능을 볼 때 보편적으로 사용했던 조합 공식은 n! / r! (n-r)! 이다.

그래서 이걸 활용하려고 했는데 그럼 어떻게 재귀하고 어떻게 DP 하는지 감이 안 옴^^

그래서 다시 찾아보니 nCr = n-1 C r-1 + n-1 C r이라는 공식이 있는 것이다. 이것은 우리에게 매우 익숙한... 피보나치의 그 느낌!

이런 점화식이 있어야 쉽게 문제를 풀 수 있다. 이걸 구현한 게  c(n-1, r-1) + c(n-1, r) 부분이다.

이렇게 top-down 방식으로 nCr의 값을 return 받는 것이다.

이걸 t번 반복해야 하기 때문에 memset을 써서 dp 배열을 초기화시켜줬다.

많이 배워갑니다^^