정수 n을 k개의 자연수로 분할하는 방법의 수

10772번: π-day

 

n개의 파이를 k명의 사람에게 분배하는데 각 사람은 적어도 1개의 파이를 받고, 앞 사람보다 적게 받을 수는 없다

 

예를 들어 7개의 파이를 5명에게 분배할려면

 

1 1 1 1 3

 

1 1 1 2 2 는 유효하지만

 

2 1 1 2 1은 유효한 경우가 아니다

 

가능한 방법의 수는?

 

--------------------------------------------------------------------------------------------------------------------------------------------

 

dp[i][j][x]를 i번째 사람에 j개 분배하고 남은 개수가 x개라고 할때 방법의 수라고 하면

 

O(N^4)에 해결할 수 있다

 

처음에 0번 사람에게 j개를 분배하면 dp[0][j][n-j] = 1

 

i = 1,2,...,k-1에서 y = j, j+1,...,x개를 분배한다고 할때, i-1번째 사람이 j = 1,2,..,n개 분배받고 남은 개수가 x개라면

 

dp[i][y][x-y] += dp[i-1][j][x]

 

dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(k)]

for j in range(1,n+1):
    
    dp[0][j][n-j] = 1

for i in range(1,k):

    for j in range(1,n+1):

        for x in range(1,n+1):
            
            for y in range(j,x+1):

                dp[i][y][x-y] += dp[i-1][j][x]

 

 

그러면 정답은? k-1번째 사람이 i개 받고 0개 남았을때 dp[k-1][i][0]를 모든 i = 1,2,..,n에 대해 더해주면

 

v = 0

for i in range(1,n+1):
    
    v += dp[k-1][i][0]

 

 

근데 당연하지만 n = 250으로 작다고 하더라도 O(N^4)은 너무 오래걸린다 이거지

 

이는 사실 integer partition 문제로 유명하다

 

https://en.wikipedia.org/wiki/Integer_partition

Integer partition - Wikipedia

 

 

 

dp[i][j] = 정수 i를 j개의 자연수로 분할하는 방법의 수

 

j개의 자연수 중 최솟값이 1이라고 하면, 나머지 j-1개에는 i-1을 분배하면 되므로 dp[i-1][j-1]

 

최솟값이 2이상이라고 한다면,  j개에 일단 1씩 분배를 하면 사용할 수 있는 자연수는 i-j

 

이 i-j를 j개에 분배하면 되므로 dp[i-j][j]

 

따라서 dp[i][j] =  dp[i-1][j-1] + dp[i-j][j]를 만족한다

 

약간 이 문제처럼 경우를 나눠 재귀적으로 점화식 세우는 거랑 비슷한듯?

 

https://deepdata.tistory.com/1398

재귀적으로 점화식 세우는 다이나믹 프로그래밍 연습1

 

 

아무튼 dp[0][0]는 아무것도 하지 않는 방법 1가지로 dp[0][0] = 1

 

i = j인 경우는 i를 i개의 자연수로 분할하는 방법의 수로 1,1,1,1,...,1로 1가지밖에 없다

 

dp[i][i] = 1

 

i = 1,2,..,n에 대하여 j = 1,2,..,k에 대해 채우면 된다

 

여기서 j > i인 경우는 정수 i를 i보다 큰 j개의 자연수 항으로 분할하는건데 불가능하므로, 

 

기본적으로 j <= i이다.

 

따라서 j = 1,2,...,min(i,k)까지 하면 된다

 

n = int(input())
k = int(input())

dp = [[0]*(k+1) for _ in range(n+1)]

dp[0][0] = 1

for i in range(1,n+1):
    
    for j in range(1,min(i,k)+1):
        
        if i == j:
            
            dp[i][j] = 1
        
        else:
            
            dp[i][j] = dp[i-j][j] + dp[i-1][j-1]
    
print(dp[n][k])

 

 

여기서 문제 조건은 오름차순으로 분배하라했는데...

 

이것도 고려해야하는거 아니야?

 

근데 분할하기만 하면 그걸 오름차순으로 정렬하면 되는거니까 상관없다

 

6 = (1,2,3), (2,3,1), (2,1,3),... 이렇게 3가지로 분할하는 방법 다 있지만 전부 다 같은 경우 1가지로 센다

 

그래서 (2,3,1)로 분할하더라도 (1,2,3)으로 해버리면 된다 이거지