[알고리즘] 다리 놓기 - DP

문제 링크

다리 놓기 : https://www.acmicpc.net/problem/1010

 

문제탐색

기본 원리 탐색

• 강 서쪽에서 강 동쪽으로 다리를 건설하는 것은 곧 M개의 수에서 N개만큼 뽑는것과 같습니다.
• 이 때, 다리가 겹치면 안된다는 것은, 뽑은 N개의 수에 순서를 정할 필요가 없다는 것입니다.
• 이것은 조합으로 C(M,N) 으로 나타낼 수 있습니다. 

 

시간복잡도와 알고리즘

• 시간제한 : 0.5초
  • 약 5000만 번의 연산이 가능하다고 가정합니다.
• 서,동 사이트 수 :  최대 29
  
  • 조합에서의 최악의 경우의수는 M과N의 최대치가 같다는 가정하에  C(M,N/2) 으로 알려져 있습니다.
  •  itertools.combinations 함수를 사용하여 모든 경우의 수를 구하면 , 최악의경우 C(29,14)가 되며 이것은 문제 예제( C(29,13) = 67863915회)에 나온것 처럼 5000만회가 넘어가며 제한시간을 초과할 가능성이 높습니다.
  • 그러므로 경우의 수를 모두 구하지않고 최선의 방법(DP+펙토리얼계산) 으로 조합계산만 진행하는 math.comb 함수를 사용합니다. 

 

=> 파이썬 math.comb 함수를 사용하여 조합을 계산 합니다.

 

 

코드설계하기

1. N과 M을 입력받습니다.
2. math.comb 함수를 사용하여 C(M,N)을 구하고 출력합니다.
3. 테스트 케이스 마다 반복합니다.

 

시도회차 수정사항

 

정답코드

import math,sys

T = int(sys.stdin.readline())

for x in range(T):
    N,M=sys.stdin.readline().split() #N과 M입력
    N,M=int(N),int(M)
    print(math.comb(M, N)) # C(M,N) 을 구한후 출력