[C#]백준 1010 다리 놓기 - Hide

반응형

https://www.acmicpc.net/problem/1010

문제 요약

다리를 지을 수 있는 경우의 수 출력하기

 

 

 

참고 1

다리끼리는 서로 겹칠 수 없다 => 사랑의 짝대기 X모양 불가능

 

 

 

M개에서 N개를 선택하는 경우의 수 공식

=> 코딩으로 구현 시

Console.WriteLine(F(m) / (F(n)*F(m-n)));

long F(int n)
{
    long s = 1;
    for (int i=2; i<= n; i++) s*=i;
    return s;    	
}

하지만 범위가 long을 벗어날 수 있다.

 

=> 분자와 분모가 겹치는 경우 미리 제거 가능

 

예를 들어 C(5,1)의 경우

4*3*2*1이 겹치기 때문에 5/1로 수식을 세울 수 있다.

 

 

 

풀이

int n = int.Parse(Console.ReadLine());
while (n-- > 0)
{
    var t = Console.ReadLine().Split().Select(int.Parse).ToArray();
    long s = 1;
    for (int i = 0; i < t[0]; i++) s = s * (t[1] - i) / (i + 1);
    Console.WriteLine(s);
}

숫자가 커질 수 있으니 s는 long형식, 곱하고 나눠야 하니까 초기값은 1.

<반복문> i는 0 ~ t[0](예제에선 2,1,13에 해당)

s*(t[1]-i)(예제에선 2,5,29에 해당)/(i+1)

---

부여알밤 롯샌 맛있음!