[BOJ][Python] 1010 다리 놓기

[문제]

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

1010번: 다리 놓기

 

[코드]

조합 문제를 푸는 방법으로 3가지가 있다. 

1. combinations 함수 사용

2. factorial 함수 사용

3. 반복문 사용

 

1. combinations 함수 사용 코드

- 시간복잡도: O(m^n)

- combinations 함수는 m개의 요소 중에서 n개의 요소를 선택하는 모든 조합을 생성한다.

- 따라서 내부적으로 m개의 요소 중에서 n개를 선택하는 모든 경우의 수를 계산하므로 O(m^n) 

- 시간복잡도가 상당하기 때문에 당연히 시간초과가 발생했다. 

#combination 사용
from itertools import combinations as c
T = int(input())
for i in range(T):
    n, m = map(int, input().split())
    x = len(list(c(range(1,m+1),n)))
    print(x)

 

2. factorial 함수 사용 코드 

- 시간복잡도: O(1)

- 파이썬의 math 모듈의 factorial 함수는 입력 값에 따라 고정된 시간이 소요된다.

- 따라서 입력 값인 m과 n의 크기에 관계없이 factorial 함수는 일정한 시간만 소요되므로 시간 복잡도는 O(1)이다. 

import math
T = int(input())

for i in range(T):
    n, m = map(int,input().split())

    print(math.factorial(m)//((math.factorial(m-n) * math.factorial(n))))

 

3. 반복문 사용 코드 

- 시간 복잡도: O(n)

- 먼저, 주어진 입력 T에 대해 T번 반복문이 실행

- 각 반복마다 변수 x와 y를 초기화하고, 두 개의 for 루프가 실행된다.

- 첫 번째 for 루프에서는 m부터 m-n+1까지 역순으로 반복하며 x를 계산하고,

- 두 번째 for 루프에서는 1부터 n까지 반복하며 y를 계산한다.

- 이러한 반복문은 입력 값인 n과 m에 비례하여 실행되므로 시간 복잡도는 O(n)

T = int(input())
for i in range(T):
    n, m = map(int,input().split())
    x, y = 1, 1
    for j in range(m,m-n,-1):
        x *= j
    for k in range(1,n+1):
        y *= k

    print(x//y)