백준 실버 5

첫번째 풀이

: m개 중에서 n개를 선택하는 모든 경우의 수이므로,
조합으로 접근했지만, 시간초과 발생함.

• 왜 발생했을까?
  : 0 < n < M < 30 이라고 함.
  조합이므로 30C30 이라는 것인데,
  대충 계산해보아도 30! 팩토리얼 정도이므로 일일이 계산하기에는 무리가
  있음.

• 어떻게 해야 할까?
  : 이미 확인한 구간에서는 미리 구한 값을 반환하도록 하자.

• 그림

  1번째 ) 2개 중에서 0개를 선택한다거나, 3개 중에서 0개를 선택하는 경우의 수는 공집합 1개이다. 이거를 이용했고,
  2번째 ) 3개 중에서 3개를 선택하는 경우의 수는 1개이다.
  왜냐하면, 다리끼리는 겹쳐서 만들수가 없다고 했기 때문에!
  

두번째 풀이

• dfs를 이용함.

• 추가적으로 위의 그림과 설명을 통한 방법으로 접근함.

• 코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;


int dp[31][31];

// 3개 중에서 3개를 선택하는 경우의 수는 모두 3개임.

// 만약에 dp[3][1] 이라면 3개 중에서 1개를 택하는 것임.
// dp[3][1] = dp[2][0] + dp[2][1];
//                1   + 2

// dp[2][1] = dp[1][0] + dp[1][1]; : 
// 2개 중에서 1개를 선택하는 것은 2개임.
//            1            1


// 2개 중에서 0개를 선택하는 것은 공집합이므로 1로 리턴하자. 


// 2개 중에서 2개를 선택하는 것은
// dp[2][2] = dp[1][1] + dp[1][2]

int  combi(int m  , int n)
{
	if (n == 0 || n == m)
	{
		dp[m][n] = 1;
		return 1;
	}

	if (dp[m][n] != 0)
	{
		return dp[m][n];
	}

	// m개 중에서 n개를 선택해야 함.

	 dp[m][n] = combi(m - 1, n - 1) + combi(m - 1, n);

	 return dp[m][n];
}


int main()
{
	//겹치면 안됨.

	// 1 2 3
	// 1 2 3 4 5

	// 조합으로 해야 할듯함. 

	// 30개 중에서 30개를 선택한다고 하면? 
	// 30의 30승 최대임

	// 팩토리얼 같은데?

	int t;
	cin >> t;

	while (t--)
	{
	

		int n, m;
		cin >> n >> m;

		cout << combi(m, n) << endl;
	}

}