[백준] 1010. 다리놓기

🗒️ 문제

강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

💭 알고리즘

📚 "다리를 총 N개 지어야하므로, 동쪽 사이트 M개 중 N개를 선택한 후 위의 사이트부터 서쪽의 1~N번째 사이트와 각각 잇는다. 그러면 다리끼리 겹치지 않으면서 N개의 다리를 설치할 수 있다. 따라서 최대 경우의 수는 mCn의 계산값과 같다. "

💬 Code

import sys
sys.setrecursionlimit(10**7)

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

T = int(input())

for test_case in range(1, T+1) :
    N, M = map(int, input().split())

    brdg = int(fact(M) / (fact(N) * fact(M-N)))

    print(f'#{test_case} {brdg}')

🤓 고려사항

1. 조합 공식은 아래와 같다.

   

2. 조합 식을 계산하기 위해서는 팩토리얼 함수를 구현해야 한다.

3. 팩토리얼의 계산 식은 f(n) = n f(n-1)* 으로, 재귀함수의 형태이다.

   return n * f(n-1)로 작성하면 return값 안에 함수 f(n-1)이 포함된 형태이므로 재귀가 잘 동작한다.

4. 팩토리얼 함수에 삽입되는 n은 0 이상의 정수이다.

   처음 작성 시, if n == 1 :로 조건을 작성했다. 따라서 M=N인 경우에서는 반환값이 없으므로 결과 값이 출력되지 않았다 😒

5. 결과 brdg는 나눗셈의 결과이므로 float 형태로 출력된다. 따라서 정수형 변환 int를 적용해주어야 한다.
   
   
   
   

🐞 보완

A

brdg = fact(M) // fact(N) * fact(M-N)

1. // 연산

// 연산은 결과값으로 나눗셈의 정수 몫을 반환하므로 int형변환이 불필요하다.

B

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

def calculate_bridge_count(N, M):
    if N == 0 or N == M:
        return 1
    return factorial(M) // (factorial(N) * factorial(M - N))

T = int(input())

for test_case in range(1, T + 1):
    N, M = map(int, input().split())

    bridge_count = calculate_bridge_count(N, M)

    print(f'#{test_case} {bridge_count}')

1. factorial의 구현은 재귀 함수 외에도 반복문으로 구현할 수 있다.
   
   
   
   

🤔 New!

• 최대 재귀한도 깊이 제한 RecursionError: maximum recursion depth exceeded in comparison
  • 에러 발생 이유
    : Python은 안정화를 위해 최대 재귀 깊이가 정해져 있다. 사용자가 정해진 깊이보다 더 깊이 재귀를 호출한다면 해당 에러가 발생하게 되는 것이다.
    
    
  • 에러 해결 방법

    import sys
    sys.setrecursionlimit(10**7)

    sys.setrecursionlimit()을 통해 python이 정해둔 최대 재귀 깊이를 변경할 수 있다.
    충분히 큰 값인 10**7로 최대 깊이를 변경하여 에러를 해결했다.