[파이썬/Python] 백준 1010번: 다리 놓기

숨·2024년 7월 12일

코테

알고리즘 문제 풀이

목록 보기

27/105

📌 문제 : 백준 1010번

📌 문제 탐색하기

N : 서쪽 사이트 수 (0 < N ≤ M < 30)
M : 동쪽 사이트 수

✅ 입력 조건
1. 테스트케이스 T 입력
2. T만큼 N, M 입력
✅ 출력 조건
1. 테스트 케이스마다 다리 지을 수 있는 경우의 수 출력
2. 한 사이트엔 최대 한 개의 다리만 연결 가능
3. 서쪽 사이트 개수(N)만큼 다리 연결
4. 다리끼리 서로 겹쳐질 수 없음

다리끼리는 서로 겹쳐질 수 없고, 서쪽의 사이트 개수만큼 다리를 연결해야 하므로 구해야 하는 경우의 수는 순서 상관없이 M개 중 N개를 뽑는 조합의 수를 계산하는 것과 같다.

itertools 라이브러리의 combinations을 활용해서 조합의 수를 구하면 될 것이라 생각했는데, 직접 조합을 다 구하다보니 시간 제한 안에 연산이 되지 않았다.

따라서 조합의 수를 바로 구할 수 있는 math 라이브러리의 comb를 활용하였다.
수학 공식으로 바로 조합의 수만 구할 수 있어 제한 시간 내에 연산이 가능하다.

가능한 시간복잡도

테스트 케이스 입력 → $O(T)$
조합의 수 계산 → $O(1)$

최종 시간복잡도
$O(T)$ 으로 제한 시간 내에 연산이 가능하다.

알고리즘 선택

math.comb를 이용해 조합의 수를 계산하기

📌 코드 설계하기

T 입력
N, M 입력
조합 구하기
원하는 형식으로 출력

📌 시도 회차 수정 사항

1회차

# 2. N, M 입력
for _ in range(T):
    N, M = map(int, input().split())

    # 3. 조합의 수 구하기
    combs = combinations(range(M), N)
    answer = len(list(combs))

    # 4. 원하는 형식으로 출력
    print(answer)

combinations로 조합을 구하고, 개수를 출력하니 예제 수행 시 연산에 매우 오랜 시간이 걸렸다.
itertools.combinations가 오래 걸리는 이유 추측
- 실제로 모든 조합을 생성해서 메모리에 저장
- 리스트로 변환해서 개수 세는 과정 필요
- 시간 복잡도 : $O(_{M}C_{N})$

# 2. 각 테스트 케이스에 대해 N, M 입력
for _ in range(T):
    N, M = map(int, input().split())

    # 3. 조합의 수 구하기
    answer = math.comb(M, N)

    # 4. 원하는 형식으로 출력
    print(answer)

바로 조합의 수를 구할 수 있는 math의 comb를 활용하였더니 문제를 해결할 수 있었다.
math.comb 특징
- 조합의 수 계산하는 수학 공식 사용
  - $k ≤ n이면, \frac{n!}{k! * (n - k)!}$
  - $k > n이면, 0$
- 조합을 직접 생성하지 않음
- 시간 복잡도 : $O(1)$
- 파이썬 3.8 이상에서만 사용 가능
- 참고 : Python Library - math

📌 정답 코드

import sys
import math

input = sys.stdin.readline

# 1. T 입력
T = int(input())

# 2. N, M 입력
for _ in range(T):
    N, M = map(int, input().split())

    # 3. 조합의 수 구하기
    answer = math.comb(M, N)

    # 4. 원하는 형식으로 출력
    print(answer)

결과

다른 풀이 1

import sys

input = sys.stdin.readline

# 1. T 입력
T = int(input())

# 2. N, M 입력
for _ in range(T):
    N, M = map(int, input().split())
	
    # 3. dp 테이블 정의
    D = [[0 for _ in range(M + 1)] for _ in range(N + 1)]
	
    # 4. dp 테이블 채우기
    for j in range(1, M+1):
        D[1][j] = j
        D[0][j] = 1

    for i in range(2, N+1):
        for j in range(i, M+1):
            D[i][j] = D[i-1][j-1] + D[i][j-1]
	
    # 5. 원하는 형식으로 출력
    print(D[N][M])

결과
파스칼의 삼각형 원리를 적용해 DP로 푼 풀이이다.
- (N, M) 크기의 DP 테이블을 정의한다.
- $_{M}C_{0}$ , $_{M}C_{1}$ 의 경우를 먼저 채운다.
- 파스칼의 삼각형 원리를 적용해 점화식을 세워 값을 채운다.
- 원하는 값을 출력한다.
시간 복잡도 : $O(T * N * M)$