[알고리즘] 백준 1010 : 다리 놓기 - S5

2023.04.15 풀이

import sys
input=sys.stdin.readline
import math 

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

2023.06.19 풀이 -> 시간초과

import sys
input=sys.stdin.readline
from itertools import combinations

t=int(input())
for _ in range(t):
    a,b=map(int, input().split())
    arr=[0]*b #list(range(b))
    print(len(list(combinations(arr, a))))

• list 생성 시 메모리 에러가 발생 -> math.comb로 리스트를 생성하지 않고 바로 개수를 구할 수 있음 : mCn - math.comb(m, n)

다른 풀이

import sys
input = sys.stdin.readline

# 다리는 겹치면 안된다.
def bridge(n,m):
    dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

    for i in range(1,m+1):
        dp[1][i] = i

    for j in range(2,n+1):
        for k in range(j,m+1):
            for l in range(k,j-1,-1):
                dp[j][k] += dp[j-1][l-1]

    return dp[n][m]

T = int(input().rstrip())
for _ in range(T):          
    n, m = map(int,input().rstrip().rsplit())
    print(bridge(n,m))  

check point

DP풀이 참고