integer partition 문제1 - 합이 k가 되는 경우의 수 구하는 다이나믹 프로그래밍 익히기(구성이 같은데 순서가 다르면 같은 경우로 세는 방법, 다른 경우로 세는 방법)

1. 문제

 

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

9095번: 1, 2, 3 더하기

 

2. 풀이

 

정수 n을 1,2,3만 사용해서 만드는 방법의 수를 구하는 문제

 

1) 여기서 1,2,3은 중복해서 사용 가능하다

 

2) 동일하게 사용해도 순서가 다르면 다르다고 취급한다.

 

즉 1+1+2와 1+2+1은 다른 경우이다.

 

dp[n]을 n을 만드는 방법의 수로 정의하고,

 

일단 n이 11보다 작기 때문에 dp의 크기를 11까지 잡아준다.

 

n을 만들려면 어떻게 해야할까?

 

1,2,3만 사용할 수 있기 때문에 3가지 경우가 가능하다.

 

1) n-1에서 1을 더하면 n 

 

n-1을 만드는 방법의 수 dp[n-1] 각각에 1만 붙여주면 되므로, dp[n-1]가지

 

2) n-2에서 2를 더하면 n

 

n-2를 만드는 방법의 수 dp[n-2] 각각에 2만 붙여주면 되므로 dp[n-2]가지

 

3) n-3에서 3을 더하면 n

 

n-3을 만드는 방법의 수 dp[n-3] 각각에 3만 붙여주면 되므로 dp[n-3]가지

 

즉, n을 만드는 방법의 수는.. dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

 

dp[0] = 0이고, dp[1] = 1이고, dp[2]는... 2, 1+1로 2가지 이고..

 

dp[3]은... dp[3] = dp[2] + dp[1] + dp[0] = 3???

 

그런데 3을 만드는 방법은 실제로 1+1+1, 1+2, 2+1, 3으로 4가지이다.

 

dp[0] = 1로 해줘야 점화식이 n=3부터 성립할 수 있지

 

dp[0] = 1로 한다는 의미는.. 0을 만드는 방법은 아무것도 안쓰는 그 자체 1가지라는 의미로 적절하다. 

 

 

#1,2,3을 사용해 n을 만드는 방법의 수
#중복 사용 가능
#1+1+2와 1+2+1은 서로 다른 방법의 수

from sys import stdin

dp = [0] * 11

dp[0] = 1

dp[1] = 1

dp[2] = 2

#n-1에 1을 더하면 n이므로 dp[n-1] 각각에 1을 붙여주면 된다
#n-2에 2를 더하면 n이므로 dp[n-2] 각각에 2를 붙여주면 된다
#n-3에 3을 더하면 n이므로 dp[n-3] 각각에 3을 붙여주면 된다
#dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
for i in range(3,11):
    
    dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

T = int(stdin.readline())

for _ in range(T):
    
    n = int(stdin.readline())
    
    print(dp[n])

 

3. 문제2

 

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

15988번: 1, 2, 3 더하기 3

 

4. 풀이

 

이 문제는 이미 업솔빙했네

 

나머지를 저장해둔다는게 시간복잡도를 줄이는데 매우 중요하다.

 

https://deepdata.tistory.com/399

정수론 - 합과 곱은 왜 계속 나눠도 문제가 없는가? -

 

 

5. 문제3

 

15989번: 1, 2, 3 더하기 4 (acmicpc.net)

15989번: 1, 2, 3 더하기 4

 

6. 풀이

 

이번엔 수의 순서가 다르더라도 같은 수들을 사용했다면 같은 경우로 센다.

 

1+2+1과 1+1+2는 서로 같은 경우이다.

 

이를 다루는 테크닉을 익혀야한다

 

n이 1만까지니까 역시 dp배열을 크기 1만까지 잡아준다

 

1) 모든 n에 대해 먼저 1로만 만들 수 있는 방법은..

 

1

 

1+1

 

1+1+1

 

1+1+1+1

 

...

 

오직 1가지씩만 가능하다

 

그래서 모든 n에 대해 dp[n]에 1을 더해준다

 

2) 다음 2도 사용할 수 있다면..?

 

1 + 1 + 2

 

2 + 2로 2가지 있는데

 

2를 제외하고 1+1과 2에서 2만 붙여준다

 

즉 4를 만드는 방법의 수 dp[4]에 2를 만드는 방법의 수인 1+1, 2 2가지를 더해준다.

 

조금 더 큰 수에 대해 생각해보면 n = 8인 경우 dp[8] = dp[7] = ... dp[1] = 1인데

 

2를 사용할 수 있다면..

 

1+1+1+1+1+1+2

 

1+1+1+1+2+2

 

1+1+2+2+2

 

2+2+2+2

 

6을 만드는 방법의 수 1+1+1+1+1+1, 1+1+1+1+2, 1+1+2+2, 2+2+2인 4가지를 더해준다.

 

근데 문제는 dp[6] = 1이 들어있는데 dp[8] += dp[6]을 하면 1만 더해지는데??

 

그래서 dp[6]을 먼저 구해야한다.

 

dp[6]에 1이 들어가 있는데, 2를 사용할 수 있다면...

 

1+1+1+1+2

 

1+1+2+2

 

2+2+2

 

4를 만드는 방법의 수인 1+1+1+1, 1+1+2, 2+2 3가지를 더해준다

 

근데 역시 dp[4]에는 1이 있어서 dp[6] += dp[4]한다고 해도 1만 더해진다..

 

그러니까 dp[4]를 먼저 구해줘야한다.

 

역시 dp[4] = 1이 들어가있는데, 2를 사용할 수 있다면...

 

1+1+2

 

2+2

 

로 2가지가 있다

 

역시 2를 만드는 방법의 수 1+1,2 2가지를 dp[4]에 더해줘야한다.

 

하지만 2에는 dp[2] = 1이 들어가있다.. 1+1을 만드는 방법 1가지

 

그래서 dp[2]도 먼저 구해줘야한다.

 

2를 사용해서 만드는 방법은..

 

2

 

로 1가지가 있다.

 

이는 0을 만드는 방법의 수 0(1가지)에 사용하는 2를 붙여준 경우이므로..

 

이래서 dp[0] = 1로 초기화해줘야한다.

 

마찬가지로, dp[0]은 0을 만드는 방법의 수인데,, 1,2,3 아무것도 사용하지 않는 그 자체 1가지로 정의하는 것이다.

 

그래서, dp[0] = 1로 초기화 하고

 

i = 1에 대하여, j = 1,2,...,8의 경우 모두 dp[j] += dp[j-1]로 계산해주면.. dp[0] = dp[1] = ... = dp[8] = 1로 먼저 구하고..

 

i = 2에 대하여 j = 0,1,2,...,8의 경우 dp[j] += dp[j-2]로 계산해주면...

 

dp[0] = 1 (1을 사용하는 방법의 수 = 1,2를 사용하는 방법의 수)

 

dp[1] = 1 (1을 사용하는 방법의 수 = 1,2를 사용하는 방법의 수)

 

dp[2] += dp[0]로 2를 만드는데 1,2를 사용하는 방법의 수 dp[2] = 2

 

dp[3] += dp[1]로 3을 만드는데 1,2를 사용하는 방법의 수 dp[3] = 2

 

dp[4] += dp[2]로 4를 만드는데 1,2를 사용하는 방법의 수 dp[4] = 3

 

dp[5] += dp[3]으로 5를 만드는데 1,2를 사용하는 방법의 수 dp[5] = 3

 

dp[6] += dp[4]로 6을 만드는데 1,2를 사용하는 방법의 수 dp[6] = 4

 

dp[7] += dp[5]로 7을 만드는데 1,2를 사용하는 방법의 수 dp[7] = 4

 

dp[8] += dp[6]으로 8을 만드는데 1,2를 사용하는 방법의 수 dp[8] = 5

 

3) 다음 3도 사용할 수 있다면..? n = 8인 경우로 조금 큰 경우를 생각해서 위와 같이 동일하게 전개해보면...

 

1+1+1+1+1+3

 

1+1+1+2+3

 

1+2+2+3

 

1+1+3+3

 

2+3+3

 

으로 5가지 있다.

 

이는 5를 1,2,3으로 만드는 방법의 수 1+1+1+1+1, 1+1+1+2, 1+1+3, 2+3, 1+2+2 5가지를 더해준 것이다.

 

근데 아직 dp[5]에는 1,2로 만드는 방법의 수 1+1+1+1+1, 1+1+1+2, 1+2+2 = 3가지만 있어서 dp[8]에 dp[5]를 더해봤자 부족하다.

 

5를 3을 사용해서 만드는 방법의 수는...

 

1+1+3

 

2+3

 

2를 1,2,3으로 만드는 방법의 수 1+1, 2 2가지를 더해줘야한다.

 

dp[2]에는 현재 1+1, 2 2가지가 이미 위에서 계산되어 저장되어 있다.

 

2는 3으로 만들 수 없으니 1,2로 만드는 방법의 수랑 1,2,3으로 만드는 방법의 수가 같겠지

 

그러므로 dp[5] += dp[2]로 5를 1,2,3으로 만드는 방법의 수는 3+2 = 5가지가 있는 것이다.

 

그래서.. i = 3에 대하여 j = 0,1,2,...,8의 경우 dp[j] += dp[j-3]으로 계산해주면...

 

dp[0] = 1 (1을 사용하는 방법의 수 = 1,2를 사용하는 방법의 수 = 1,2,3을 사용하는 방법의 수)

 

dp[1] = 1 (1을 사용하는 방법의 수 = 1,2를 사용하는 방법의 수 = 1,2,3을 사용하는 방법의 수)

 

dp[2] = 2(1,2를 사용하는 방법의 수 = 1,2,3을 사용하는 방법의 수)

 

dp[3] += dp[0]로 3을 만드는데 1,2,3를 사용하는 방법의 수 dp[3] = 2+1 = 3

 

dp[4] += dp[1]로 4를 만드는데 1,2,3를 사용하는 방법의 수 dp[4] = 3 + 1 = 4

 

dp[5] += dp[2]으로 5를 만드는데 1,2,3를 사용하는 방법의 수 dp[5] = 3 + 2 = 5

 

dp[6] += dp[3]로 6을 만드는데 1,2,3를 사용하는 방법의 수 dp[6] = 4 + 3 = 7

 

dp[7] += dp[4]로 7을 만드는데 1,2,3를 사용하는 방법의 수 dp[7] = 4 + 4 = 8

 

dp[8] += dp[5]으로 8을 만드는데 1,2,3를 사용하는 방법의 수 dp[8] = 5 + 5 = 10

 

어떻게 더하고 있는지를 관찰할 필요가 있다

 

예시를 들어 한번 점검해보니 느낌이 오긴하네...

 

그러면 다음 2가지 테크닉을 외우고 사용하자

 

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

 

요약하자면..

 

1) 다음과 같이 n을 먼저 고정하고 사용할 수 있는 도구인 1,2,3으로 반복문을 돌면..

 

1,2,3 더하기 3 문제처럼 구성은 같은데 순서가 다르면 다른 경우로 세는 경우의 수가 나온다

 

#모든 N에 대해, 사용할 수 있는 도구 1,2,3으로 반복문을 돈다
# = 구성이 같아도 순서가 다르면 다른 경우
dp = [0]*10001

dp[0] = 1

for j in range(1,10001):
    
    for i in range(1,4):
        
        if j - i >= 0:
            
            dp[j] += dp[j-i]

 

2) 근데 반대 순서로 돌면 구성이 같은데 순서가 달라도 같은 경우로 세는 경우의 수가 나온다.

 

즉 사용할 수 있는 도구 1,2,3에 대해 반복문을 돌고 다음 모든 n= 1,2,3,..,10000에 대해 반복문을 돌면서

 

dp[n] += dp[n-j]를 해주면.. 순서가 달라도 같은 경우로 세는 경우의 수가 나온다

 

#합이 k가 되는 경우의 수를 세는 방법
#구성이 같은데, 순서가 달라도 같은 경우로 세는 경우의 수
from sys import stdin

dp = [0]*10001

dp[0] = 1

#사용하는 도구 1,2,3 먼저 돌고
#모든 n에 대해 돌아야 순서가 달라도 같은 경우로 센다
for i in range(1,4):
    
    for j in range(1,10001):
        
        if j - i >= 0:
            
            dp[j] += dp[j-i]

T = int(stdin.readline())

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

    print(dp[n])

 

7. 문제4

 

2293번: 동전 1 (acmicpc.net)

2293번: 동전 1

 

8. 풀이

 

n가지 동전을 사용해서, k원을 만드는 방법의 수를 구하는 문제

 

"사용한 동전의 구성이 같은데 순서만 다른 것은 같은 경우"

 

사실상 위 1,2,3 더하기 4와 동일한 문제다.

 

사용할 수 있는 도구 n가지 동전을 순회해서 그 가치가 i라 한다면, 이에 대해 0~k까지 순회해서 dp[j] += dp[j-i]로 채워 넣는다

 

from sys import stdin

n,k = map(int,stdin.readline().split())

money = []

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

    money.append(m)

dp = [0]*(k+1)

dp[0] = 1

#N가지 도구를 사용해 합이 K가 되는 방법의 수 
#구성이 같은데 순서가 다르면 같은 경우로 세는 방법의 수
#도구를 먼저 순회하고, 목표로 만들고자 하는 0~K를 순회한다
for m in money:
    
    for i in range(1,k+1):
      
      if i >= m:
          
          dp[i] += dp[i-m]

print(dp[k])

 

 

9. 문제5

 

16400번: 소수 화폐 (acmicpc.net)

16400번: 소수 화폐

 

10. 풀이

 

역시 위와 동일한 문제로, 도구를 사용해 합이 K가 되는 경우의 수를 세는 문제

 

그런데 구성이 같은데 순서가 달라도 같은 경우로 센다.

 

역시 도구를 먼저 순회하고, 목표값 0~K를 순회하는 방식으로 DP배열을 채워넣는다.

 

N이하의 소수를 모두 찾기 위해 에라토스테네스의 체를 이용하고, 그렇게 찾은 소수 리스트가 도구가 될 것

 

이를 먼저 순회하고, 0~N을 순회해서 DP배열을 채워넣자.

 

나머지를 요구하기 때문에, 매번 더할때마다 나눠줘서 나머지를 저장하면 시간복잡도를 줄일 수 있을 것이다.

 

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]

n = int(stdin.readline())

prime_list = get_prime(n)

dp = [0]*(n+1)

dp[0] = 1

for p in prime_list:
    
    for i in range(2,n+1):
        
        if i-p >= 0:
            
            dp[i] += dp[i-p]
            dp[i] %= 123456789

print(dp[n] % 123456789)