[백준] 다리 놓기 - DP

문제 보러 가기

해당 문제는 백준 DP 알고리즘 분류에서 Silver 5 문제입니다.

문제 설명은 생략하고 제가 생각한 풀이를 적어보겠습니다.

참고로, 저는 C++ 언어를 사용합니다.

같이 생각해보기?

왼쪽의 다리와 오른쪽 다리를 연결합니다. 또한 다리는 각 1대1로 대응되어 건설됩니다.

이때 다리 건설은 서로 겹치지 않는다고 했으니, 무조건 1대1 대응이 확정입니다.

그렇다면 다리의 수는 항상 오른쪽 구역이 더 많은데 서로 중복되는게 없어야 한다?

즉 순서는 상관 없지만, 중복되는 것을 빼고 계속 뽑는다는 의미겠죠? 예, 조합을 의미합니다.

오른쪽 기준 내가 왼쪽 구역에서 다리를 선택하겠어! 라는 생각으로 문제를 접근해봅시다.

 

시작 전에 조합 공식 기억나시나요? 여기 있습니다!! 출처는 인터넷 ㅎ

피보나치를 쓰면 간단하죠! 왜냐? 사실상 nCr = (n-1)C(r-1) + (n-1)Cr 이니 정말 간단합니다. 그런데 피보나치의 함수를 call하는게 많아지다 보니 stack에 점차 쌓여 stackoverflow가 생길 수 있습니다. 또한 시간 복잡도도 n이 커지면 엄청 빠르게 커지겠죠 그러면 메모이제이션! 할 수 있게 배열을 만들어서 저장하면 되는거 아닌가요? 가능합니다!

하나는 n 하나는 r로 사용할거니깐 int dp[n][r] 이런식으로 선언하고 n을 오른쪽 다리 수 r은 왼쪽 다리수로 하면 되겠네요

c++를 조금 이용해보면 vector<int, vector<int>> dp (n, vector<int>(r)) 이런식의 2차원 배열도 만들 수 있습니다.

 

내가 생각한 풀이

하지만 저는 조금 다른 방법을 생각했습니다. (사실 학교에서 알고리즘 수업 같이 듣다보니 dp과제 했는데, 2차원 배열 선언하는게 크게 좋은거 같진 않더라고요... 개인적인 생각입니다ㅠ)

이 식을 응용해보면 결국 분자는 n부터 (n-r+1) 까지 곱하는 거고 분모는 r부터 1까지 곱해서 나눕니다.

이제 문제에 맞춰 변수를 바꿔보면, n은 동쪽 다리 수 m이고 r은 서쪽 다리수 n으로 가정하면 mCn입니다!

즉 분자가 m이고 분모가 n인 분수에서 -1 씩 하면서 곱해가면 되는겁니다!!

#include<iostream>
#include<vector>

int main(void)
{
	int testCase = 0;
	int n = 0, m = 0; //서쪽, 동쪽 다리

	std::cin >> testCase;
	for (int i = 0; i < testCase; i++)
	{
		std::cin >> n >> m;

		long long dp = 1;

		int r = 1;
		for (int j = m; (m - n) < j; j--)
		{
			// (m * m-1 * ... * m - r + 1) / (n * n-1 * .... * 1) 임을 이용
			// m/n 에서 시작하여 m과 n을 각각 1씩 줄이면서 곱하자
			dp *= j;
			dp /= r;
			r += 1;
		}
		std::cout << dp << std::endl;
	}
	return 0;
}