1. 문제 풀이
다리 놓기는 일직선 모양의 강의 동쪽과 서쪽에 다리를 겹치지 않게 놓을 수 있는 경우의 수를 구하는 문제이다.
서쪽과 동쪽에는 각 N개와 M개의 다리를 둘 수 있는 곳이 있고 0 < N ≤ M < 30 으로 주어진다.
해당 문제는 위의 경우의 수를 구하는 공식을 통해 풀이했다.
위의 공식을 코드로 옮겼을 시에는 long long 오버플로우로 중복되어 곱해지는 부분을 제외해 주었고
제외 할 수는 m - n or n 중 큰수로 m! 계산에서 제거하였다.
2 . 코드
#include <iostream>
using namespace std;
int main() {
int m;
int n;
int ca;
//테스트케이스 개수
cin >> ca;
//경우의 수
long long count = 1;
for (int i = 0; i < ca; i++)
{
cin >> n;
cin >> m;
int j = 0;
count = 1;
// 중복연산 제외할 n 설정
if (n > m - n)
n = m - n;
//m! 연산, n보다 큰 수까지만 곱한다
while (j < n)
{
count *= m - j;
j++;
}
j = 0;
//count를 n보다 작은 수까지 나눈다.
while (j < n)
{
count /= j + 1;
j++;
}
cout << count << endl;
}
return 0;
}
C++
복사
3. 채점 기록
메모리 : 2016KB / 시간 : 16ms
