백준 / 1010번 / 다리 놓기 / Python / 수학,DP,조합

📚문제

출처 : 백준 1010번(https://www.acmicpc.net/problem/1010)

📝풀이

# 1010번 다리 놓기(Silver V)

# 1.다이나믹 프로그래밍 사용 X
def factorial(n):
    cnt = 1
    for i in range(1,n+1):
        cnt *= i
    return cnt

t = int(input())
for i in range(t):
    n,m = map(int,input().split())
    ans = int(factorial(m) / (factorial(n)*factorial(m-n)))
    print(ans)

첫 번째 풀이방법은

동쪽 사이트 M개 중 

서쪽 사이트 N개를 고르는 문제라

조합으로 풀면된다

 

조합 공식은 기억이 안 나서 해당 링크를 참고했다

https://ko.wikipedia.org/wiki/%EC%A1%B0%ED%95%A9

조합 - 위키백과, 우리 모두의 백과사전

공식만 알면 factoria을 구해서 대입하면 되기 때문에

간단하게 풀 수 있다

---

# 2.다이나믹 프로그래밍 사용 O
dp = [[0]*30 for _ in range(30)]
for i in range(30):
    for j in range(30):
        if i==1:
            dp[i][j] = j
        else:
            if i==j:
                dp[i][j] = 1
            elif i<j:
                dp[i][j] = dp[i-1][j-1] + dp[i][j-1]

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

 

두 번째 풀이방법은

알고리즘 분류에 다이나믹 프로그래밍이 있어서

다이나믹 프로그래밍 풀이방법에 익숙해질 겸 참고하였다

 

다이나믹 프로그래밍이 나올 때마다 용어가 잘 기억이 안나고 생소한데

간단하게 점화식이라고 기억해놓으면 좋을 것 같다

 

어떤 문제를 풀기 위해 그 문제를 더 작은 문제들의 연장선으로 생각하고 과거에 구한 해를 활용하는 문제해결 패러다임
출처 : 나무위키

 

dp 배열에서

해당 코드가 어떻게 나오게 되는지

백준 1010번 Python 다이나믹 프로그래밍 풀이

[백준] 1010번 다리 놓기 (파이썬)

해당 링크에서 아주 잘 설명해주셔서 참고했다