다리 놓기

백준 1010번 문제입니다.

📌 문제 설명

상세 설명: https://www.acmicpc.net/problem/1010

• 강 주변에 다리를 지으려고 한다. 서쪽에는 N개의 사이트, 동쪽에서 M개의 사이트가 있다.
• 서쪽의 사이트와 동쪽의 사이트를 다리로 연결한다.
• 서쪽의 사이트 개수만큼(N개) 다리를 짓는다. 단, 다리끼리는 서로 겹쳐질 수 없다.
• 이때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성해야 한다.
  
• 입력 첫 줄에는 테스트 케이스의 개수 T
• 그 다음 줄부터는 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트 개수가 주어진다. (N, M / 0 < N <= M < 30)
• 출력은 각 테스트 케이스에 대한 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

📌 문제 풀이

두 가지로 문제를 풀 수 있다. 일단, 문제를 읽자마자 조합의 경우를 생각해 볼 수 있었다.

# factorial 정의
def factorial(N):
	if N > 1:
    	return (N * factorial(N-1))
    else:
    	return 1
        
# T 입력 받기
T = int(input())
for _ in range(T):
	N, M = map(int, input().split())
    print(factorial(M) // (factorial(M-N) * factorial(N)))

• 위 코드는 factorial을 정의한 후, 이것을 활용하여 풀이 한 것이다.
• 마지막 줄의 print(factorial(M) // (factorial(M-N) * factorial(N)))은 조합 공식을 활용한 것이다.
  
  

다른 방법으로도 해결할 수 있는데, 이 방법은 하단의 그림을 바탕으로 작성된 코드이다.

T = int(input())
dp = [[0] * 30 for _ in range(30)] #N, M / 0 < N <= M < 30 조건에 의거
for i in range(30):
    for j in range(30):
        if i == 1:
            dp[i][j] = j #위 그림에서 볼 수 있듯, N==1이면 M의 개수가 경우의 수를 결정
        else:
            if i == j:
                dp[i][j] = 1 #N=M이면 경우의 수는 하나뿐
            elif i < j:
                dp[i][j] = dp[i-1][j-1] + dp[i][j-1]

for _ in range(T):
    N, M = map(int, input().split())
    print (dp[N][M])