백준 - 1010번 다리놓기 python 문제풀이 [Hellfer]

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

1010번: 다리 놓기

🔷 알고리즘 분류 - 다이내믹프로그래밍,  조합론

난이도 - 실버 5

파이썬의 math 모듈에는 수학적 연산을 수행하는 다양한 함수들이 포함되어 있습니다. 이 중 일부는 다음과 같습니다:

1. math.ceil(x): x보다 크거나 같은 가장 작은 정수를 반환합니다. (올림)
2. math.floor(x): x보다 작거나 같은 가장 큰 정수를 반환합니다. (내림)
3. math.factorial(x): x의 팩토리얼 값을 계산합니다.
4. math.gcd(a, b): 두 정수 a와 b의 최대공약수(GCD)를 반환합니다.
5. math.sqrt(x): x의 제곱근을 계산합니다.
6. math.exp(x): e의 x 제곱 값을 계산합니다.
7. math.log(x [, base]): base를 밑으로 하는 x의 로그 값을 계산합니다. base가 지정되지 않으면 자연로그를 계산합니다.
8. math.pow(x, y): x의 y 제곱 값을 계산합니다.
9. math.sin(x), math.cos(x), math.tan(x): 각각 x의 사인, 코사인, 탄젠트 값을 계산합니다. x는 라디안 단위입니다.
10. math.pi: 원주율 π (pi) 값을 가지고 있습니다.
11. math.e: 자연 상수 e 값을 가지고 있습니다.

🔶첫 번째 풀이 - 조합론을 이용한 풀이

# math 모듈을 가져옵니다.
import math

# 테스트 케이스의 수를 입력 받습니다.
t = int(input())
for _ in range(t):
    # 각 테스트 케이스마다 서쪽과 동쪽 사이트의 개수를 입력 받습니다.
    n, m = map(int, input().split())

    # 조합의 공식을 이용해 동쪽 사이트에서 서쪽 사이트 개수만큼 선택하는 경우의 수를 계산합니다.
    # mCn = m! / (n!(m-n)!)
    bridge = math.factorial(m) // (math.factorial(n) * math.factorial(m - n))

    # 계산된 경우의 수를 출력합니다.
    print(bridge)

🔶두 번째 풀이 - 다이내믹프로그래밍을 이용한 풀이

# 테스트 케이스의 수를 입력 받습니다.
t = int(input())

# 30x30 크기의 2차원 DP 테이블을 0으로 초기화합니다.
dp = [[0]*30 for _ in range(30)]

# DP 테이블을 채웁니다.
for i in range(30):
    # 각 행의 첫 번째 열과 대각선 위치는 1로 초기화합니다.
    dp[i][0] = 1
    dp[i][i] = 1

    # 각 행의 나머지 열은 이전 행의 이전 열 값과 이전 행의 같은 열 값을 더하여 계산합니다.
    for j in range(1, i):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

# 각 테스트 케이스에 대해 조합을 계산하여 출력합니다.
for _ in range(t):
    # 서쪽 사이트의 개수 n과 동쪽 사이트의 개수 m을 입력 받습니다.
    n, m = map(int, input().split())

    # mCn을 DP 테이블에서 찾아 출력합니다.
    print(dp[m][n])

🔶 초보자를 위한 첫 번째 문제 코드풀이

파이썬의 math 모듈에 있는 factorial 함수는 정수 n의 팩토리얼 값을 계산해 주는 함수입니다.

팩토리얼이란, 양의 정수 n에 대해 1부터 n까지의 모든 정수의 곱을 말합니다. 수학적으로 n!로 표현되며

n! = n * (n-1) * (n-2) *... * 3 * 2 * 1로 계산됩니다. 예를 들어, 5의 팩토리얼은 5! = 5 * 4 * 3 * 2 * 1 = 120입니다.

파이썬에서는 math.factorial(n)을 통해 n의 팩토리얼 값을 바로 계산할 수 있습니다.

예제 코드는 다음과 같습니다.

import math

n = 5
print(math.factorial(n))  # 출력: 120

 

위 코드는 5의 팩토리얼 값을 계산하여 출력합니다.

🔶초보자를 위한 두 번째 문제 코드풀이

# 각 행의 나머지 열은 이전 행의 이전 열 값과 이전 행의 같은 열 값을 더하여 계산합니다.
    for j in range(1, i):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

 

이 코드의 핵심은 조합의 성질인 "nCr = n-1Cr-1 + n-1Cr"를 이용하여, 이전에 계산한 조합의 결과를 이용해 현재의 조합을 계산한다는 것입니다.

예를 들어, 5C3을 계산하려면 이전에 계산한 4C2와 4C3의 결과를 더하면 됩니다.

이를 코드로 표현하면 다음과 같습니다:

 

dp[5][3] = dp[4][2] + dp[4][3]

 

따라서, 2차원 DP 테이블 dp [i][j]에서 dp [i][j]는 dp [i-1][j-1]과 dp [i-1][j]의 합이 됩니다.

이렇게 이전에 계산한 값을 활용함으로써, 중복된 계산을 줄이고 효율적으로 문제를 해결하는 것이 가능해집니다.  이것이 바로 다이내믹 프로그래밍의 핵심 아이디어입니다.

 

🤗파이팅입니다~ 여러분!!🤗