합분해 2225번 백준

문제:www.acmicpc.net/problem/2225

2225번: 합분해

이 문제의 경우 dp를 팩토리얼 개념으로 접근하다가 틀린 케이스다.

 

import sys
N,K= map(int,sys.stdin.readline().rstrip().split())
dp = [-1]*202
div=1000000000
dp[0]=1
dp[1]=1
def factorial(n):
    if n==1 or n==0:
        return 1
    if dp[n]!=-1:
        return dp[n]
    dp[n]=(n*factorial(n-1))
    return (n*factorial(n-1))
factorial(N+1)
ans=dp[N+1]/(dp[N+1-K+1]*dp[K-1])
 
ans%=div
print(int(ans))

문제를 처음 접근 방법은 수학 조합으로 접근하였다. 예를 들어 5라는 숫자가 있다면 1 1 1 1 1 이렇게 다섯 개가 존재하고 K는 칸막이로서 K-1개의 칸막이를 1사이의 공간과 맨 왼쪽,오른쪽 공간 중 어디에 놓느냐에 따라 결정되는가로 접근해서 풀었다. 하지만 문제에서는 K가 N보다 더 클 수 있었다는 것에서 이미 이 풀이는 틀렸다. 만일 K가 N보다 작거나 같다는 조건이 있었다면  .

 

import sys 
N, K = map(int, sys.stdin.readline().split()) 
mod = 1000000000 
table = [1] 
table += [0] * N 
for _ in range(1, K+1): 
    for idx in range(1, N+1): 
        table[idx] = (table[idx] + table[idx-1])%mod 
sys.stdout.write(str(table[N]))
 

[2][4]의 경우에도 알아보자.

(0을 1개의 숫자로 만드는 경우의 수)*(3를 1개의 숫자로 만드는 경우의 수)

+ (1을 1개의 숫자로 만드는 경우의 수)*(2을 1개의 숫자로 만드는 경우의 수)

+ (2를 1개의 숫자로 만드는 경우의 수)*(1을 1개의 숫자로 만드는 경우의 수)

+ (3를 1개의 숫자로 만드는 경우의 수)*(0을 1개의 숫자로 만드는 경우의 수)

=[1][1]*[1][4]+ [1][2]*[1][3]+ [1][3]*[1][2]+[1][4]*[1][1]=4

 

정답코드를 보면 알 수 있지만 코드에서는 2차원이 아닌 1차원으로 해결하였다. 이것은 위에 참고한 블로그에서 보면 좋을 것 같다.