BOJ
[BOJ] 다리놓기(1010) - PYTHON
허비1411
2022. 5. 25. 22:44
강이 위에서 아래로 흐르고 서쪽, 동쪽 땅으로 구분돼있다. 서쪽과 동쪽에는 각각 다리를 놓을 수 있는 포인트들이 N, M개 있다. (M >= N) 이때 서쪽에서 동쪽으로 다리를 놓으려고 할 때 다리를 놓을 수 있는 최대 경우의 수를 찾는 문제다.
시간 복잡도: O(MN)
풀이과정
강의 서쪽 땅 N개의 포인트에서 동쪽 땅 M개의 포인트를 연결하고자 하며, N은 M보다 작거나 같다. 이때 강의 동쪽에 연결할 M개의 포인트 중에 N개를 선택하면 서쪽에서 이어질 다리가 교차하면 안 되므로 다리를 짓는 경우가 1개 나온다. 즉 M개의 포인트에서 N개를 선택하는 경우의 수가 이 문제의 정답이다.

주의할점
조합은 수가 커질수록 결괏값이 커지므로 수의 범위를 조심해야 한다. 문제에서는 M, N의 최댓값이 30이기 때문에 나올 수 있는 수의 최댓값은 155117520으로 int범위를 벗어나지 않는다. Python3부터는 int값 이상도 표현할 수 있지만 다른 언어로 작성하면 combination을 구할 숫자가 커질 때 주의가 필요하다.

코드
1
2
3
4
5
6
7
8
9
10
11
12
|
N = int(input())
for _ in range(N):
n, m = map(int, input().split())
bigNum = 1
smallNum = 1
while n >= 1:
bigNum *= m
smallNum *= n
m -= 1
n -= 1
print(bigNum // smallNum)
|
주석 추가
1
2
3
4
5
6
7
8
9
10
11
12
13
|
N = int(input())
for _ in range(N):
n, m = map(int, input().split()) # M, N 입력
bigNum = 1 # (M-N)!이 될 수
smallNum = 1 # N!이 될 수
while n >= 1: # N이 1이될때까지 bigNum에 M, smallNum에 N을 곱하고 1씩 뺀다
bigNum *= m
smallNum *= n
m -= 1
n -= 1
print(bigNum // smallNum)
|
cs |
채점 결과
