integer partition 문제 2 - m개 이하의 수만 사용해서 합이 k가 되도록 만드는 경우의 수 구하는 다이나믹 프로그래밍

1. 문제

 

15992번: 1, 2, 3 더하기 7 (acmicpc.net)

15992번: 1, 2, 3 더하기 7

 

2. 풀이

 

저번엔 사용 개수의 제한 없이 합을 n으로 만드는 방법을 배웠다면..

 

https://deepdata.tistory.com/951

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

 

1,2,3을 중복해서 사용하는데 m개만 사용해서 합을 n으로 만드는 경우의 수를 구하는 방법을 배운다.

 

n을 만드는데 몇개의 수를 사용했는지 정보를 기억하고 있어야겠지

 

dp[i][j]를 1,2,3으로 i를 만드는데 j개를 사용하는 경우의 수라고 정의할때...

 

j-1개를 이용해 i-1을 만드는 경우의 수 dp[i-1][j-1] 각각에 1을 붙여주고

 

j-1개를 이용해 i-2를 만드는 경우의 수 dp[i-2][j-1] 각각에 2를 붙여주고

 

j-1개를 이용해 i-3을 만드는 경우의 수 dp[i-3][j-1] 각각에 3을 붙여주면..

 

이 경우의 수들을 모두 합해주면 j개의 수로 i를 만드는 dp[i][j]가 되겠지

 

순서가 다르면 다른 경우의 수로 세므로, 1~n을 먼저 순회하고, 사용하는 도구를 순회한다

 

이렇게 dp배열을 채우면 dp[n][m]은 "m개의 수를 사용해 n을 만드는 경우의 수"가 된다

 

#m개의 1,2,3을 중복해서 사용해 n을 만드는 경우의 수
#순서가 다르면 다른 경우의 수로 센다
from sys import stdin

mod = 1000000009

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

dp[1][1] = 1
dp[2][1] = 1
dp[2][2] = 1
dp[3][1] = 1
dp[3][2] = 2
dp[3][3] = 1

#dp[i-1][j-1] 각각에 1을 붙여주고
#dp[i-2][j-1] 각각에 2를 붙여주고
#dp[i-3][j-1] 각각에 3을 붙여주고
#이들을 모두 더해주면 j개의 수로 i를 만드는 경우의 수
#순서가 다르면 다른 경우의 수로 세니 n = 1~1000을 먼저 순회함
for i in range(4,1001):
    
    for j in range(1,i+1):
                    
        dp[i][j] += (dp[i-1][j-1] + dp[i-2][j-1] + dp[i-3][j-1])
        dp[i][j] %= mod

T = int(stdin.readline())

for _ in range(T):
    
    n,m = map(int,stdin.readline().split())
    
    print(dp[n][m]) #dp[n][m]은 m개의 수로 n을 만드는 경우의 수

 

처음에는 이렇게 풀었는데

 

from sys import stdin

mod = 1000000009

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

dp[1][1] = 1
dp[2][1] = 1
dp[2][2] = 1
dp[3][1] = 1
dp[3][2] = 2
dp[3][3] = 1

for i in range(4,1001):
    
    for j in range(1,i+1):
        
        for k in range(1,4):
            
            dp[i][j] += dp[i-k][j-1]
            dp[i][j] %= mod

T = int(stdin.readline())

for _ in range(T):
    
    n,m = map(int,stdin.readline().split())
    
    print(dp[n][m] % mod)

 

시간이 2배정도 걸리더라고..? 다음과 같이 하면 mod로 나누는 연산을 4번하기 때문에 느려지는것 같다

 

나누는 연산이 오래걸리거든

 

        for k in range(1,4):
            
            dp[i][j] += dp[i-k][j-1]
            dp[i][j] %= mod

 

3. 문제2

 

16195번: 1, 2, 3 더하기 9 (acmicpc.net)

16195번: 1, 2, 3 더하기 9

 

4. 풀이

 

이번엔 m개 이하의 수를 사용해서 n을 만드는 방법의 수를 구하는 문제

 

위와 완전히 동일한데, dp[n][i]가 i개의 수를 사용해 n을 만드는 경우의 수이므로,

 

dp[n][1] + dp[n][2] + dp[n][3] + ... + dp[n][m]이 m개 이하의 수를 사용해서 n을 만드는 경우의 수가 될 것이다.

 

#m개 이하의 1,2,3을 중복해서 사용해 n을 만드는 경우의 수
#순서가 다르면 다른 경우의 수로 센다
from sys import stdin

mod = 1000000009

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

dp[1][1] = 1
dp[2][1] = 1
dp[2][2] = 1
dp[3][1] = 1
dp[3][2] = 2
dp[3][3] = 1

#dp[i-1][j-1] 각각에 1을 붙여주고
#dp[i-2][j-1] 각각에 2를 붙여주고
#dp[i-3][j-1] 각각에 3을 붙여주고
#이들을 모두 더해주면 j개의 수로 i를 만드는 경우의 수
#순서가 다르면 다른 경우의 수로 세니 n = 1~1000을 먼저 순회함

for i in range(4,1001):
    
    for j in range(1,i+1):
                    
        dp[i][j] += (dp[i-1][j-1] + dp[i-2][j-1] + dp[i-3][j-1])
        dp[i][j] %= mod

T = int(stdin.readline())

for _ in range(T):
    
    n,m = map(int,stdin.readline().split())
    
    answer = 0
    
    #dp[n][i] = i개의 수를 사용해 n을 만드는 경우의 수
    #dp[n][1] + dp[n][2] + ... + dp[n][m] = m개 이하의 수를 사용해 n을 만드는 경우의 수
    for i in range(1,m+1):
        
        answer += dp[n][i]
        answer %= mod
    
    print(answer)