[백준/1010/파이썬] 다리놓기

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

Problem

• 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다.재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다.
• 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

조건

• 이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.
• 다리끼리는 서로 겹쳐질 수 없다
• 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다.
• 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

SOL

mCn의 식을 가지는 조합의 문제이다.

고등학교 수학 때, 이런 문제 많이 풀어봤다. (라떼는 확률과 통계 문,이과 통합과목이였다)

m개 다리 중 , n개의 다리를 선택해서, 겹치지 않게 놓기만 하면 된다. (서로 겹칠 수 없고, 1개의 다리만 가능하므로, 1가지만 존재함)

combination, factorial 등등을 다 이용해도 되지만, 이항정리를 이용해서 Top-down 형식으로 1개,

bottom up 방식으로 1개 , 2가지 방법으로 구현 해보려고한다.

# 조합의 수이다.
# 이항 정리를 이용하면 아래와 같다. 
# Top -down
# F(m,n) = F(m-1,n-1) + F(m-1,n)
tc= int(input())

def sol(n,r):
    if DP[n][r] !=0:
        return DP[n][r]
    if r==1:
        return n
    elif n==r:
        return 1
    else:
        DP[n][r] = sol(n-1,r-1) + sol(n-1,r)
    return DP[n][r]

while tc:
    r,n =map(int,input().split())
    DP=[[0]*(r+1) for _ in range(n+1)]
    print(sol(n,r))
    tc-=1

#bottom-up
tc=int(input())

while tc:
    r,n = map(int,input().split())
    DP = [[0]*(r+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,r+1):
            if j==1:
                DP[i][j] = i
            elif i==j:
                DP[i][j] = 1
            else:
                DP[i][j]=DP[i-1][j-1] + DP[i-1][j]
    print(DP[n][r])
    tc-=1