Algorithm TIL (241012)

[백준] 2225 합분해 

https://www.acmicpc.net/problem/2225

🔥 다시 풀어보기 🔥

 

 

문제 분석

• 0부터 N까지 정수 K개를 선택해 그 합이 N개가 되는 경우의 수를 구해야 한다.
• 선택하는 숫자들은 중복될 수 있다.

 

처음 아이디어

• 중복 순열을 구해서 합이 n이 될 때를 비교해 count를 1 증가해준다.

 

틀린 문제 풀이 : 시간 초과

from itertools import permutations, product
import sys
input = sys.stdin.readline

n,k = map(int,input().split())
cnt = 0
# 중복 순열 중에서 n이 되는 경우 카운트한다.
for p in product(range(n+1), repeat=k) :
    if sum(p) == n :
        cnt += 1
        
print(cnt%1000000000)

 

이유 분석

• product 메서드의 시간복잡도는 모든 조합의 개수와 비례한다. 때문에 n^k 개의 조합을 생성한다. 
• 즉, 생성되는 조합의 개수에 비례하여 지수 시간복잡도를 가진다.

 

다른 아이디어 (참고)

• 다이나믹 프로그래밍
• 아래의 사진이 이해하기 좋았다.

• 예를 들어 n = 5, k = 3 일 때, 합이 n이 되기 위해 더할 마지막 숫자가 a라고 할 때, x + x + a = n 이다.
• (n-a) + a = n 으로 즉, 이전까지의 숫자의 합에 n이 될 수 있는 임의의 숫자를 더하면 된다는 결론이 나온다.
• 이를 DP 배열로 표현하자면, DP[k][n] = DP[k-1][0] + DP[k-1][1] + ... + DP[k-1][n]
• 즉 다시 풀어 설명하자면 k-1개의 수에서 0~n 까지 만드는 방법의 수를 모두 더한다. 마지막에 어떤 수가 오던지 단 1가지만 오게 되어 있으니 모든 경우의 수를 더하면 현재 k개의 숫자로 n을 만들 수 있게 된다.
• 내가 참고했던 블로그도 참조한다. (https://hongjw1938.tistory.com/63, https://computer-choco.tistory.com/545)

 

수정한 코드

from itertools import permutations, product
import sys
input = sys.stdin.readline
n,k = map(int,input().split())

# dp[k][n] = 0~N의 숫자 중 k개를 더해 n을 만들 수 있는 경우의 수
dp = [[0]*(n+1) for _ in range(k+1)] 

# 초기화
dp[0][0] = 1

for i in range(k+1) : 
    for j in range(n+1) :
    	# dp[i-1][0]부터 dp[i-1][j]까지 더한다.
        for l in range(j+1) :
            dp[i][j] += dp[i-1][j-l]
            
print(dp[k][n] % 1000000000)

 

배운 점

• 시간 제한이 우려된다면 itertools permutations, combinations 의 사용은 지양하자. 시간초과 가능성이 높다.
• 숫자를 k개를 합해 n을 만들 때, (n-a) + a = n 의 개념을 기억해두고 이를 어떻게 효율적으로 사용할 지 고민하자.
• (n-a) 은 k-1개 + a 은 1개 = n 은 k개의 합