1010번 다리놓기

문제링크 : www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

<문제풀이 접근법>

 1) 최대로 다리를 지을 수 있어야 함으로 N개의 사이트에는 모두 다리가 지어져야한다.

 2) 다리끼리 겹칠 수 없기 때문에 순서를 고려하지 않는 경우의 수로 구해야한다. 

   => MCN 방법(조합) 이용

        우측에 있는 M개의 사이트 중 N개를 고르고 좌측의 N개의 사이트에 위에서 부터 순서대로 연결한다.

 

 

방법 1. 파스칼 삼각형 이용( 메모리 : 28776KB  시간 : 112ms)

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    N,M = map(int, sys.stdin.readline().split())
    fascal = [[1 for _ in range(M+1)]for _ in range(M+1)]
    for i in range(0,M+1):
        for j in range(0,i+1):
            if((i==j) | (j==0)):
                fascal[i][j] = 1
            else:
                fascal[i][j] = fascal[i-1][j-1]+fascal[i-1][j]
    print(fascal[M][N])

 

방법 2. for문을 통해 MPN/N!이용( 메모리 : 28776KB  시간 : 64ms)

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    N,M= map(int,sys.stdin.readline().split())
    total =1
    if(N!=M):
        for i in range(M,M-N,-1):
            total*=i
        for j in range(N,1,-1):
            total//=j
    print(total)