문제접근
1.
첫번째 접근
강 서쪽의 N개의 사이트에서 강 동쪽의 M개의 사이트를 연결 짓는 경우의 수를 찾는 문제이다.
위의 식을 구현을 하면 되는 문제이고, 조합관련 함수 안에 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])
}
C++
복사
→ 자료형에 대해 고려가 부족
놓쳤던 부분
이 공식을 사용하게 되면 나누는 과정에서 쓸 자료형이 애매해지게 된다.
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);
}
C++
복사
