[백준]1010 다리놓기(Python)

문제

• 링크
  

• 강 좌우로 N개와 M개의 포지션을 연결하는 문제, 최대 N개는 무조건 놔야함

• 한번 지으면 그 전의 point는 연결할 수 없음

로직 및 풀이정리

• 사실 M개중 N개를 뽑고 순서정렬하기만 하면 되는 문제임
• 순서상관없는 조합문제
• 수식 :

CODE

def factorial(n:int) -> int:
    n_fac = 1
    for i in range(1, (n+1)) : # n!
        n_fac = n_fac * i
    return n_fac

loop_num = int(input())
for _ in range(loop_num):
    n, m = map(int, input().split())
    bridge_num = int(factorial(m) / (factorial(m-n) * factorial(n)))
    print(bridge_num)

후기 및 다른사람 코드

• 조합이 아니라 그냥 factorial만 기억나서 그걸로 주구장창 풀다가 답답해서 찾아보니 조합이었다...
• factorial도 n * (n-1) * ... * 1로 생각이 굳어져서 어렵게 하려다보니 잘 안풀렸고, 또 저 수식 자체를 함수화 하는게 아니라 n * (n-1)을 함수화 하려고하니까 더 꼬였다. 하나배움!
• int(factorial(m) / (factorial(m-n) * factorial(n))) 이 아니라 몫을 나타내는 //을 사용했으면 더 의미적으로 맞는 식이 나왔을 것 같다

# math 모듈을 사용한 방법
import math

T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    bridge = math.factorial(m) // (math.factorial(n) * math.factorial(m - n))
    print(bridge)

와 dp(동적계획법)?로도 풀수 있나본데??

• dp로 푼 풀이
  
  
  역시 알수록 신기한 알고리즘의 세계....