[백준/13707/파이썬] 합분해 2

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

13707번: 합분해 2

Problem

• 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
• 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

조건

• 첫째 줄에 두 정수 N(1 ≤ N ≤ 5,000), K(1 ≤ K ≤ 5,000)가 주어진다.

SOL

O(N^2)내에 풀어야 하는 문제이다. 그래서, DP로 풀거나, 수학적인 방법으로 밖에 풀지못함.

합분해 1은 완전탐색으로 3중반복을 하면 풀린다고 한다.

DP를 그대로, python으로 갖다쓰니까, 시간초과가 나버려서, pypy3로 제출했더니 통과가 되었음.

아마 python3로 통과를 하려면, 수학적인 식을 내거나, 더 최적화를 해야할 거 같다.

# 0 부터 N까지 정수 K개를 더해서, 그 합이 N이 되는 경우 

N,K=map(int,input().split())
DP=[[0]*(N+1) for _ in range(K+1)]

DP[1] =[1]*(N+1)

for i in range(1,K+1):
    DP[i][0] = 1
#print(DP)
for i in range(2,K+1):
    for j in range(1,N+1):
        DP[i][j] = (DP[i-1][j]+DP[i][j-1])%1000000000

print(DP[K][N])

수학적인 방법

• a+b+c = 6인 경우의 수를 구한다고 생각해보자. (단, a,b,c는 0이상의 정수)
• a+b+c = 6이라고한다면, 이렇게 생각해볼 수도 있다. 애기때, 블록놀이를 하는것 처럼, 1짜리 공 6개와 +기호 2개만 있으면, 6을 표현할 수 있다.
• ||OOOOOO 라고한다면, (0+0+6)이 될거고, O|OO|OOO 라고 한다면, (1+2+3)이 될거다.
• 경우의 수를 구해준다면, (n+k-1)!/n!*(k-1)!이 되버린다. 이는, n+1Hk-1과 같음!
• 고등학교때, 확률과 통계 문제가 생각난다.(라떼는, 미적2,기벡,확통이였따 이마리야)

def fac(n):
    sum =1
    for i in range(1, n+1):
        sum *= i
    return sum

n, r = map(int, input().split())
print((fac(n+r-1)//(fac(r-1)*fac(n)))%1000000000)