[Python] 백준 알고리즘 1010번 - 다리 놓기

[Python] 백준 알고리즘 1010번 - 다리 놓기

 

문제 출처: 1010번: 다리 놓기 (acmicpc.net)

1010번: 다리 놓기

P1010

접근 방법

접근은 조합으로 접근을 하였다.
1 ) 파이썬 자체 내장 팩토리얼 메서드 이용
2 ) 팩토리얼을 동적계획법으로 구하고 그 나온 수를 이용해서 조합의 구조로 답출력

동적계획법을 넣기 위해 2번의 방식을 선택했다. 문제에서 주어진 숫자의 범위는
0 <= n <= m < 30이다. 즉 팩토리얼을 29까지만 계산 후 원하는 답의 형태로 뽑아내고 출력하는 방식을 선택했다.

시간 복잡도는 초반에 동적계획법을 사용하는 o(n) * 타겟팅 번호를 출력하는 o(1)
최종 시간복잡도는 O(n)이라고 생각합니다.

조합 : [Python] 백준 알고리즘 2407번 - 조합 (tistory.com)

[Python] 백준 알고리즘 2407번 - 조합

기존 조합 문제와 다르게 팩토리얼 부분을 다이나믹 프로그래밍의 메모이제이션 기법을 사용해서 구했다.

 

풀이코드

 

t = int(input())

memo = [1 for i in range(30)]
for i in range(2, 30):
    memo[i] = i * memo[i - 1]

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