[백준 1010 파이썬] 다리 놓기 (실버5, 조합론)

알고리즘 유형 : 조합론
풀이 참고 없이 스스로 풀었나요? : O

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

SOLVE 1

팩토리얼 재귀 함수 풀이

import sys
input = sys.stdin.readline

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n-1)

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    # 구하는 것은 mCn
    
    print(factorial(M) / (factorial(M-N) * factorial(N)))

SOLVE 2

조합 공식 변형($_{n}\mathrm{C}_{k}$ = n(n-1)(n-2)...(n-k+1) / k!)을 활용한 시간 복잡도를 최소화한 풀이

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    divided = 1
    for i in range(N):
        divided *= M
        M -= 1
        
    divisor = 1
    for i in range(2, N+1):
        divisor *= i
        
    print(divided // divisor)

입력 크기가 작아서 굳이 DP로 안 풀어도 되는 문제

SOLVE 1) 풀이 요약 (팩토리얼 재귀 함수 풀이)

1. 팩토리얼 재귀 함수 구현

2. 조합 공식 그대로 활용해서 답 구하기($_{n}\mathrm{C}_{k}$ = n! / (n-k)!k!)

SOLVE 2) 풀이 요약 (조합 공식 변형($_{n}\mathrm{C}_{k}$ = n(n-1)(n-2)...(n-k+1) / k!)을 활용한 시간 복잡도를 최소화한 풀이)

1. 공식 그대로 for 돌리면서 구현하면 된다.

배운 점, 어려웠던 점

1. 장황한 문제 설명을 읽고, 그 속에서 핵심 원리를 찾아 간단한 수학 문제로 바꿔 푸는 능력 향상

2. 비슷한 유형 문제 풀이로 인한 구현력 및 문제 해결 능력 성장!