integer partition4 -서로 다른 소수의 합으로 자연수를 만드는 방법의 수(역으로 순회하는 테크닉)-

1. 문제

 

3908번: 서로 다른 소수의 합 (acmicpc.net)

3908번: 서로 다른 소수의 합

 

2. 풀이

 

소수만을 사용하는데, 서로 다른 소수를 사용해야하고 k개를 사용해서 합했을때 n을 만드는 방법의 수를 구하기

 

일단 도구로 소수를 구해야겠지

 

n이 최대 1120이니까 1120이하의 소수를 모두 에라토스테네스의 체로 구해놓고

 

def get_prime(n):
    
    result = [1]*(n+1)

    for i in range(2,int(((n+1)**(1/2)))+1):
        
        if result[i] == 1:
            
            for j in range(i*i,n+1,i):
                
                result[j] = 0
    
    return [i for i in range(2,n+1) if result[i] == 1]

prime = get_prime(1120)

 

dp[n][k]를 n을 k개의 서로 다른 소수로 만드는 방법의 수라고 정의하면...

 

k개를 이용해 i를 만드는 방법의 수 dp[i][k]는 k-1개로 i-p를 만드는 방법의 수 dp[i-p][k-1] 각각에 소수 p만 더해주면 된다

 

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

dp[0][0] = 1

for p in prime:
    
    for k in range(1,15):
        
        for i in range(1,1121):

            if i >= p:

                dp[i][k] += dp[i-p][k-1]

 

근데 이렇게 하면 생각하는 경우보다 더 많이 나오더라고...

 

예를 들어 dp[24][3]을 하면 3이 나오더라고 정답은 2인데

 

2 5 17

2 3 19

2 11 11

 

소수 p가 작은값부터 시작해서, k = 1,2,3,...으로 순회할텐데...

 

p = 11에서 k = 2에서 dp[13][2] += dp[2][1]에 2,11을 셀거고...

 

다시 k = 3이 될때, dp[24][3]에 보면 p = 11에서 dp[24][3] += dp[13][2]이 세질거니까.. 2,11,11이 세지는것

 

하지만 중복해서 소수를 사용하면 안된다

 

이를 위해 k를 k=14,13,...,1로 역으로 세는 방법을 사용

 

그러면 p = 11일때 k = 3에서... dp[24][3] += dp[13][2]로 될것이지만... k = 2를 아직 도달하지 못했으니...

 

dp[13][2] = 0이 있어서 2 11을 아직 만들지 못했다..

 

그러다가 k = 2가 되면 dp[13][2] += dp[2][1]인데 p = 2, k = 1에서 dp[2][1] = 1로 이미 저장되어 있으니 

 

dp[13][2] = 1로 여기서 구해진다.

 

즉, k = 14,13,...,1로 역으로 세준다면 dp[24][3]에서 2,11,11처럼 소수를 중복해서 사용하는 경우를 피할 수 있게 된다

 

#서로 다른 소수를 k개 사용해서 n을 만드는 방법의 수

from sys import stdin

def get_prime(n):
    
    result = [1]*(n+1)

    for i in range(2,int(((n+1)**(1/2)))+1):
        
        if result[i] == 1:
            
            for j in range(i*i,n+1,i):
                
                result[j] = 0
    
    return [i for i in range(2,n+1) if result[i] == 1]

prime = get_prime(1120)

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

dp[0][0] = 1

#k개의 소수로 i를 만드는 방법의 수는..
#k-1개의 소수로 i-p를 만드는 방법의 수 각각에 p만 더해주면 된다
#구성이 같은데 순서가 달라도 같은 것으로 취급할려면, 도구 소수부터 순회해서..
for p in prime:
    
    #k를 역으로 순회해줘야 dp[24][3]에 2,11,11같이 중복해서 소수를 사용하는 경우를 방지한다
    for k in range(14,0,-1):
        
        for i in range(1,1121):

            if i >= p:

                dp[i][k] += dp[i-p][k-1]
            
T = int(stdin.readline())

for _ in range(T):
    
    n,k = map(int,stdin.readline().split())

    print(dp[n][k])