1010번: 다리 놓기

문제접근🤔

1. 첫번째 접근

   강 서쪽의 N개의 사이트에서 강 동쪽의 M개의 사이트를 연결 짓는 경우의 수를 찾는 문제이다.

   $$ mCn = \frac {m!}{(m-n)!\times n!} $$

   위의 식을 구현을 하면 되는 문제이고, 조합관련 함수 안에 factorial 연산을 하는 함수를 따로 만들어 구현을 하면 될 거 같다.

   factorial 연산이 세번이 필요하여 그때마다 재귀호출을 통해서 구하는 것보다 m! 전까지를 memoization을 해두고 쓰게 되면 반복적인 계산 과정을 생략 할 수 있어서 더 효율적이지 않을까 생각한다.

   //pseudo code
   vector<double> dp
   
   while (m까지)
   	dp[i] = dp[i-1] * i
   
   void combination()
   {
   	cout << dp[m] / (dp[m-n] * dp[m])
   }
   

   → 자료형에 대해 고려가 부족

놓쳤던 부분😅

$$ mCn = \frac {m!}{(m-n)!\times n!} $$

이 공식을 사용하게 되면 나누는 과정에서 쓸 자료형이 애매해지게 된다.

long long 을 사용해서는 오버플로우가 나기 때문에 원하는 결과를 얻을 수 없고, double 을 사용하는 것은 오차범위 때문에 정확한 값을 얻을 수가 없어진다.

따라서, iomanip 헤더에서 정밀도 조정을 통해서 출력값을 조정했다

코드😁

2016 KB

0 ms

#include <iostream>
#include <vector>
#include <iomanip>

std::vector<double> dp;
int t;
int n, m;

void input_setting()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	std::cin >> t;
}

void factorial_memoization()
{
	int i = 1;

	dp[0] = 1;
	dp[1] = 1;
	while (++i <= m)
		dp[i] = dp[i - 1] * i;
}

void solution()
{
	std::cout << std::setprecision(15);
	while (t--)
	{
		std::cin >> n >> m;
		dp.resize(m + 1);
		factorial_memoization();
		std::cout << dp[m] / (dp[m - n] * dp[n]) << "\\n";
	}
}

int main(void)
{
	input_setting();
	input();
	solution();
	return (0);
}