문제 이해하기
n개의 사탕과 k개의 가방이 있다고 가정해 보겠습니다. 우리가 구해야 할 값은 모든 가방에 최소 한 개 이상의 사탕이 들어가도록 사탕을 분배할 수 있는 방법의 총 개수입니다. 여기서 중요한 전제는 모든 사탕이 서로 다르다는 점입니다. 따라서 어떤 사탕이 어느 가방에 들어가느냐에 따라 달라지는 모든 조합을 빠짐없이 세어야 합니다.
예를 들어 입력이 n = 3, k = 2라고 하면, 출력은 3이 됩니다.
사탕을 나눌 수 있는 방법은 다음과 같습니다.
(1, 2), (3)
(1), (2, 3)
(2), (1, 3)
해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 풀이 과정은 다음과 같습니다.
크기가 n x n인 2차원 배열 dp를 선언하고 모든 값을 1로 초기화합니다.
c를 2부터 n-1까지 반복합니다.
b를 1부터 min(c, k) - 1까지 반복합니다.
점화식에 따라 dp[c][b] := dp[c-1][b-1] + dp[c-1][b] × (b+1) 로 값을 갱신합니다.
최종적으로 dp[n-1][k-1]을 결과로 반환합니다.
여기서 dp[c][b]는 첫 번째부터 c번째 사탕까지를 b+1개의 가방에 나누어 담는 방법의 수를 의미합니다. 새로운 사탕을 추가할 때는 두 가지 선택지가 존재합니다. 첫째, 이미 존재하는 b+1개의 가방 중 하나에 넣는 경우(dp[c-1][b] × (b+1))이고, 둘째, 새로운 가방을 만들어 단독으로 넣는 경우(dp[c-1][b-1])입니다. 이 두 경우를 모두 더하면 원하는 답을 얻을 수 있습니다.
구현 예시
다음 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(n, k):
dp = [[1] * n for _ in range(n)]
for c in range(2, n):
for b in range(1,min(c,k)):
dp[c][b] = dp[c-1][b-1] + dp[c-1][b] * (b+1)
return dp[n-1][k-1]
print(solve(3, 2))입력
3, 2
출력
3
복잡도 분석
이 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n × k)이며, n x n 크기의 dp 테이블을 사용하므로 공간 복잡도는 O(n²)입니다. n과 k가 크지 않은 범위에서는 매우 빠르게 동작합니다.