integer partition 문제 3 - 서로 다른 자연수를 사용해서 특정한 자연수 n을 만드는 방법의 수는 홀수만을 사용해서 만드는 방법의 수와 같다(count number of partition of n)

1. 문제

 

9764번: 서로 다른 자연수의 합 (acmicpc.net)

9764번: 서로 다른 자연수의 합

 

2. 풀이

 

dp[j][i]를 1부터 i까지의 자연수 중에서 최대 하나씩만 사용해서 j를 만드는 방법의 수라고 정의하자.

 

여기서 구성이 같은데 순서가 달라도 같은 방법으로 취급한다

 

https://deepdata.tistory.com/951

합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은

 

그러면 도구 i를 1부터 2000까지 먼저 순회하고, 목적이 되는 j를 나중에 순회하는 방식으로 해결할 수 있다.

 

여기서 dp[j][i]를 어떻게 구할 수 있을까?

 

1부터 i까지 사용해서 합해서 j를 만들려면 당연히 i는 j 이하의 수여야한다.

 

1부터 i-1까지의 수를 사용해서, j-i를 만드는 방법의 수(dp[j-i][i-1])들 각각에 i만 더해주면 된다.

 

여기에 1부터 i-1까지의 수를 사용해서 이미 j를 만드는 방법의 수(dp[j][i-1])도 역시 i를 사용하진 않았지만, 

 

1부터 i까지의 수를 사용해서 j를 만드는 방법의 수와 같으므로 더해준다.

 

즉, $$dp[j][i] = dp[j-i][i-1] + dp[j][i-1]$$

 

 

하지만, i > j인 경우는 어떨까?

 

그것도 정의할 수 있는데, 그거는 i를 쓰지 않고 j를 만들 수 있기 때문에.. 1부터 i-1까지의 수를 사용해서 j를 만드는 방법의 수와 같다.

 

즉, $$dp[j][i] = dp[j][i-1]$$이다.

 

이를 정의하는 이유는 1부터 2000까지 dp배열을 채워나갈건데, 결국에 dp[2000][2000]을 만들기 위해...

 

dp[5][2000]이라든지 dp[1000][2000]이라든지 이런게 필요해서 그렇다

 

그러면 1부터 n까지의 수를 사용해서, n을 만드는 방법의 수는 dp[n][n]에 저장되어 있다.

 

dp[0][i] = 1로 초기화해야하는데, i = j인 경우 dp[j][i] = dp[0][i-1] + dp[j][i-1]로 dp[0][i]꼴의 값이 필요해서 그렇다.

 

from sys import stdin

#dp[j][i] = 서로 다른 1부터 i까지 사용해서 j를 만드는 방법의 수

mod = 100999

dp = [[0]*2001 for _ in range(2001)]

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

for i in range(1,2001):
    
    for j in range(1,2001):
        
        if i <= j:
            
            #1부터 i-1만을 사용해서 j-i를 만드는 방법의 수에 i만 더해주고
            #1부터 i-1만을 사용해서 j를 만드는 방법의 수에는 이미 j니까 
            #그것도 1부터 i까지 사용해서 만드는 방법의 수이며
            #굳이 i를 안더해줘도 되는
            dp[j][i] = dp[j-i][i-1] + dp[j][i-1]
        
        else:
            
            #i > j이면, i를 안쓰고 j를 만들 수 있으므로..
            
            dp[j][i] = dp[j][i-1]
        
        dp[j][i] %= mod

T = int(stdin.readline())

answer = 0

for _ in range(T):
    
    n = int(stdin.readline())

    print(dp[n][n])

 

 

3. 다른 풀이

 

In number theory and combinatorics, a partition of a non-negative integer n, also called an integer partition, is a way of writing n as a sum of positive integers.

 

음이 아닌 정수 n의 partition이란, 자연수의 합으로 n을 나타내는 방법의 수를 말한다.

 

이러한 partition을 구하는 문제는 유명한 문제이며.. 연구가 많이 되어 있다.

 

https://en.wikipedia.org/wiki/Partition_(number_theory)#Odd_parts_and_distinct_parts

Partition (number theory) - Wikipedia

 

여기서 수학자 오일러(Leonhard Euler)가 증명한 놀라운 정리가 

 

"서로 다른 자연수만을 사용해서 자연수 n을 나타내는 방법의 수(patition with distinct parts)는 홀수만을 중복해서 사용해서 자연수 n을 나타내는 방법의 수(partition with odd parts)와 같다"

 

이를 이용하면 1차원 배열로 빠르고 쉽게 해결할 수 있다.

 

dp[i]가 홀수를 사용해 i를 만드는 방법의 수라고 정의한다면... 구성이 같은데 순서가 달라도 같다고 취급하자.

 

그러면 홀수 배열을 도구로 만들고, 도구 i를 먼저 순회하고, 목적이 되는 i를 나중에 순회해서...

 

j - i를 만드는 방법의 수 각각에 i만 더하면 i를 만드는 방법의 수가 되므로... dp[j] += dp[j-i]이다.

 

from sys import stdin

mod = 100999

dp = [0]*2001

dp[0] = 1

odd = list(range(1,2001,2))

for i in odd:

    for j in range(1,2001):
        
        if j - i >= 0:

            dp[j] += dp[j-i]
            dp[j] %= mod

T = int(stdin.readline())

for _ in range(T):
    
    n = int(stdin.readline())

    print(dp[n])