[백준] 1010번 다리놓기 (실버)

m >=n 일 때 n개의 다리를 놓을 수 있는 경우의 수를 구하는 문제이다. 

 

n만큼 뽑아서 순서대로 놓으면 되기 때문에 조합의 수를 구하면 된다.

 

 

1. 내 풀이 

 

5C2의 경우 n=2이고 m=5 이다. 

n 의 개수만큼 5*4 5부터 1씩 빼면서 곱해주고 거기서 다시 n인 2부터 n의 개수만큼만 곱한 수를 나눠주면 된다

다시 말하면 5*4 / 2*1 이 답이다.

n=3인 경우는 3개씩이니까 5*4*3 / 3*2*1 이다.

import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
    n, m = map(int, input().split())
    answer=1;
    mm=m;
    for _ in range(n):
        answer*=mm
        mm-=1
    for i in range(n,0,-1):
        answer=answer//i
    print(answer)

    

 

2. 다른 사람의 풀이 

 

factorial을 구해놓고 푸는 좋은 방법을 봤다 

실행시간과 메모리 사용은 위 풀이와 같았다.

import sys
input=sys.stdin.readline
t=int(input())

# 팩토리얼이 담기는 배열
factorial=[1,1] # factorial[0] =1 이다

for i in range(2,30): # m이 30보다 작다 
    factorial.append(factorial[-1]*i)

for _ in range(t):
    n, m = map(int, input().split())
    print(factorial[m]//factorial[n]//factorial[m-n])