[백준][DP] 1010번 다리놓기

문제

서쪽의 N개의 사이트, 동쪽의 M개의 사이트가 주어질 때 다리를 놓을 수 있는 경우의 수를 구하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1010)

풀이

꽤 간단한 문제인데 (혼자) 함정아닌 함정에 빠져서 1시간정도 걸린 문제입니다. 동쪽에 M개의 사이트로 N개의 다리를 놓는 경우의 수이고 모든 다리는 똑같이 생겼을 것이기 때문에 조합의 수와 같다고 할 수 있습니다. 처음에 생각을 하지 않고 풀었는지 이 문제가 dp일까? 하면서 조합을 구하는 공식 n!/k!(n-k)! 을 바로 적용해버렸습니다. 테스트케이스는 올바르게 나왔지만 신중히 제출하기 위해 질문검색을 찾아보니 바로 오버플로우가 나는 것을 알 수 있었습니다. N, M이 30이하이지만 30!만 해도 int 범위를 벗어난다는 것을 고려하지 못했습니다. 해결하기위해서는 dp로 풀어야했습니다. 점화식 접근 자체는 쉬웠는데 n, m을 바꿔서 i, j로 생각하다보니 잘못 수식을 작성해서 잘 풀리지 않았었습니다. N개의 다리를 M개에 놓는 경우를 최종적으로 구하기 위해서 M개중에 N개를 고르는 조합을 구하는 공식을 응용해서 점화식을 세웠습니다. 차례대로 식을 변형시켜보겠습니다. dp[m][n] =  m!/(n!(*m-n)!) -> dp[m][n-1] = m!/((n-1)!*(m-(n-1))!) = m!*n/(n!*(m-n+1)*(m-n)!) = dp[m][n]*n/(m-n+1)  -> dp[m][n] = dp[m][n-1]*(m-n+1)/n 라는 결과가 나오게 됩니다. 보통 i번째의 값을 이용해서 i+1을 구하도록 점화식을 생각하는데 여기서는 n에서 n-1으로의 점화식을 만들어버려서 계산하는데 시간이 오래 걸려버렸습니다.. 그리고 2차원 배열이기때문에 이중 for문을 통해서 값을 업데이트시킬 때 m과 n을 어떠한 순서로 증가시켜야될 지 고민이 됐습니다. 그와함께 n이 1일 때의 문제가 떠올랐는데 모든 m에 대해서 dp[i][1]은 i라는 것을 통해 순서에 대한 고민을 없앨 수 있었습니다. 처음 dp[i][1]을 초기화 해준 다음 m과 n을 2에서 시작하는 이중for문으로 만들어주었습니다.

코드

https://github.com/kswim/Algorithm/blob/master/DP/1010.cpp