[백준/Python] 1010번: 다리놓기 (조합)

1. 문제

1010번: 다리 놓기

2. 해결

 

조합 - 고등 확률과 통계에서 배운 내용이 나왔다.

 

n,m중 하나씩 선택하는 경우의 수를 구하는데 ..

이때 다리가 겹치면 안되니 동쪽의 사이트는 앞서 선택된 사이트 번호보다 큰 수를 선택해야한다. 즉, n개의 사이트를 구하지만 이때 순서는 상관이 없다. 왜냐하면 자동으로 순서가 정해지거든 ! 그래서 조합으로 -> mCn을 구하면 답이다 ~~ ! 

 

** 문제의 제한 덕분에 가능했던 것 같다. n,m<=30 이라는 조건이 있었다 .

O(N!)이지만 .. 문제에서 나올 수 있는 가장 큰 값인 n!(n−m)!∗m!=155117520 을 생각해보았다. 물론 컴퓨터로 알아보았다. .! 

최댓값이지만 10억을 넘지 않는다 !

 

다이나믹 프로그래밍 - 작은 문제로 쪼개서 생각하기 .. 

 

이 문제는 dp로도 풀 수 있었다.

예를 들어서 

dp(2,5) = dp(1,4) + dp(1,3) + dp(1,2) + dp(1,1)

dp(3,5) = dp(2,4) + dp(2,3) + dp(2,2) 

              = {dp(1,3)+dp(1,2)+dp(1,1)} +{dp(1,2) + dp(1,1) } + { dp(1,1) }

 

여러번 해보면 

dp(n,m) = dp(n-1, m-1) + dp(n-1, m-2) + dp(n-1,m-3) ... +dp(n-1,n-1) 이고 하나씩 dp를 적용하면 된다 ~~ ! 

 

 

3. 코드 

import math

def bridge(m,n):
    case = math.factorial(m) / (math.factorial(m-n)*math.factorial(n))

    return case

t=int(input())
for _ in range(t):
    n,m = map(int,input().split())
    print(int(bridge(m,n)))

 

 

** 다이나믹 프로그래밍을 배워서 다른 코드 포스팅 업로드 하기