백준 - 11051번 이항 계수 2 python 문제풀이 [Hellfer]

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

11051번: 이항 계수 2

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

난이도 - 실버 2

 

1. 지수와 로그 함수: math.exp(x), math.log(x [, base]), math.log2(x), math.log10(x)

 

import math

print(math.log(100, 10))  # 밑이 10인 로그 100 계산

2. 제곱근 함수: math.sqrt(x)

 

import math

print(math.pow(2, 3))  # 2의 3제곱 출력, 결과: 8.0
print(math.sqrt(9))    # 9의 제곱근 출력, 결과: 3.0

3. 삼각함수: math.sin(x), math.cos(x), math.tan(x)

 

import math

print(math.sin(math.pi/2))  # sin(pi/2) 계산, 결과: 1.0
print(math.cos(math.pi))    # cos(pi) 계산, 결과: -1.0

4. 쌍곡선 함수: math.sinh(x), math.cosh(x), math.tanh(x)

5. 제곱, 제곱근: math.pow(x, y), math.sqrt(x)

6. 절댓값: math.fabs(x)

7. 반올림: math.ceil(x), math.floor(x)

8. 팩토리얼: math.factorial(x)

 

import math

print(math.factorial(5))  # 5 팩토리얼 계산, 결과: 120

9. 이항 계수: math.comb(n, k)

 

import math

print(math.comb(5, 2))  # 5개 중에서 2개를 선택하는 조합의 수, 결과: 10

10. 최대공약수: math.gcd(a, b)

🔶문제 풀이 - math함수 이용

# math 모듈을 import 합니다.
import math

# 사용자로부터 두 개의 정수 n과 m을 입력 받습니다.
n, m = map(int, input().split())

# math.comb(n, m)을 통해 이항 계수를 계산합니다. 
# n개 중에서 m개를 선택하는 방법의 수를 나타냅니다.

print(math.comb(n, m) % 10007)

🔶문제 풀이 - 다이내믹 프로그래밍 이용

# 정수 n과 k를 입력 받습니다.
n, k = map(int, input().split())

# dp 리스트를 초기화합니다.
dp = [[0 for _ in range(1001)] for _ in range(1001)]

# dp[0][0]의 값을 1로 설정합니다.
dp[0][0] = 1

# 1부터 n까지의 각 원소에 대하여
for i in range(1, n+1):
    # 0부터 i까지의 각 원소에 대하여
    for j in range(i+1):
        # i와 j가 같거나, j가 0일 경우, dp[i][j]의 값을 1로 설정합니다. 
        # 이는 i개 중에서 i개를 선택하거나, 0개를 선택하는 방법은 1가지입니다.
        if i == j or j == 0:
            dp[i][j] = 1
        # 그 외의 경우, dp[i][j]의 값을 dp[i-1][j-1]과 dp[i-1][j]의 합으로 나타냄.
        else:
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod

# 최종적으로 dp[n][k]를 출력합니다.
print(dp[n][k])

🔶문제 이해하기

import math

n,m=map(int,input().split())

print(math.comb(n,m)%10007)

 

예를 들어, 5 3이라고 입력한다고 가정해 보겠습니다.

 

이는 n=5, m=3을 의미하며, 5개의 원소 중에서 3개를 선택하는 방법의 수를 계산하겠다는 것입니다.

그러면 코드는 math.comb(5, 3)을 통해 이항 계수를 계산하게 됩니다. 

 

이는 5개의 원소 중에서 3개를 선택하는 방법의 수를 나타내며, 계산 결과는 10이 됩니다.

 

for i in range(1,n+1):
    for j in range(i+1):
        if i==j or j==0:
            dp[i][j]=1
        else:
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%10007

 

 

먼저, 입력 값으로 n=4와 k=2를 가정해봅시다. 

 

이는 4개의 원소 중에서 2개를 선택하는 방법의 수를 구하려는 것을 의미합니다.

코드는 1부터 n(=4)까지의 각 원소에 대해서, 0부터 i까지의 각 원소에 대해 연산을 진행합니다. 

 

이 때, dp[i][j]는 i개의 원소 중에서 j개를 선택하는 방법의 수를 나타냅니다.

코드를 차례대로 실행해보면 다음과 같습니다:

1. i=1일 때:
j=0일 때: dp[1][0] = 1 (1개 중에서 0개를 선택하는 방법은 1가지)

j=1일 때: dp[1][1] = 1 (1개 중에서 1개를 선택하는 방법은 1가지)

2. i=2일 때:

j=0일 때: dp[2][0] = 1 (2개 중에서 0개를 선택하는 방법은 1가지)
j=1일 때: dp[2][1] = (dp[1][0] + dp[1][1]) % 10007 = 2 (2개 중에서 1개를 선택하는 방법은 2가지)
j=2일 때: dp[2][2] = 1 (2개 중에서 2개를 선택하는 방법은 1가지)

3. i=3일 때:
j=0일 때: dp[3][0] = 1 (3개 중에서 0개를 선택하는 방법은 1가지)
j=1일 때: dp[3][1] = (dp[2][0] + dp[2][1]) % 10007 = 3 (3개 중에서 1개를 선택하는 방법은 3가지)
j=2일 때: dp[3][2] = (dp[2][1] + dp[2][2]) % 10007 = 3 (3개 중에서 2개를 선택하는 방법은 3가지)
j=3일 때: dp[3][3] = 1 (3개 중에서 3개를 선택하는 방법은 1가지)

4. i=4일 때:
j=0일 때: dp[4][0] = 1 (4개 중에서 0개를 선택하는 방법은 1가지)
j=1일 때: dp[4][1] = (dp[3][0] + dp[3][1]) % 10007 = 4 (4개 중에서 1개를 선택하는 방법은 4가지)
j=2일 때: dp[4][2] = (dp[3][1] + dp[3][2]) % 10007 = 6 (4개 중에서 2개를 선택하는 방법은 6가지)
j=3일 때: dp[4][3] = (dp[3][2] + dp[3][3]) % 10007 = 4 (4개 중에서 3개를 선택하는 방법은 4가지)
j=4일 때: dp[4][4] = 1 (4개 중에서 4개를 선택하는 방법은 1가지)

이렇게 모든 연산을 마치면 dp[4][2]의 값은 6이 됩니다.

 

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