[백준] 2407번 조합(python)(dp)

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

2407번: 조합

 

1. 난이도 실버3 (🥈) 

 

2. 내가 작성한 코드

 

dp 공부중이라 dp로 해결하고 싶었는데, 파스칼의 삼각형 공식을 제대로 몰라서 지저분하게 풀었다. 머쓱,,

 

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

dp = [0] * (n+1)
dp[1] = 1 
dp[n] = n

for i in range(2,m+1):

  if n-i < i: #nCm n-m>m인 경우
    dp[i] = dp[n-i] #nCn-m값 넣어줌

  else: #nCm 직접 계산해줌
    r = n
    d = i
    for j in range(1,i):
      r *= (n-j) #f
      d *= (i-j)
    dp[i] = r // d

print(dp[m])

 

3. 추가 공부

이항 계수를 구하는 공식은 아래와 같으며

 

import math

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

num1 = math.factorial(n)
num2 = math.factorial(m) * math.factorial(n-m)

print(num1//num2)

from math import comb

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

print(comb(n,m))

이 공식을 토대로 factorial 혹은 comb 를 이용해서 풀 수 있다.

 

 

 

파스칼이 삼각형을 이용하면 nCm = n-1Cm + n-1Cm-1 의 점화식을 이용해 문제를 해결할 수 있다.

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

dp = [[0 for i in range(101)] for j in range(101)]

for i in range(1,101):
    dp[i][0] = 1
    dp[i][i] = 1

for i in range(2,101):
    for t in range(1,i):
        dp[i][t] = dp[i-1][t-1] + dp[i-1][t]
        
print(dp[n][m])