1. 문제
https://www.acmicpc.net/problem/2225
2. 문제 이해
0부터 N까지의 정수 중에 아무 수나 K개(중복 가능)를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제입니다.
예를 들어 N이 5이고 K가 3이면,
위 그림과 같이 21가지입니다.
3. 해결 방법
가. 동적 프로그래밍
숫자가 K개가 될 때까지 하나씩 추가해가며 합이 N보다 작거나 같은 경우의 수를 관리해봅시다.
먼저, 숫자를 1개만 사용하면 경우의 수는 각각 고른 숫자만큼 합이 되므로 경우는 모두 각각 1가지 입니다.
다음으로 숫자를 2개 사용하는 경우에는 이전에 숫자 1개를 사용하여 만든 값을 활용하여 빠르게 계산할 수 있습니다.(DP)
이렇게 표를 채워가면 3중 for문으로 채워지게 됩니다.(행, 열, 이전 행)
그러나 굳이 이전 행을 다 살펴보지 말고, 이전 열에서 계산한 값을 다시 재사용해서 채우면 2중 for문으로 채울 수 있습니다.(행, 열)
2. 비슷한 문제
위 그림에서 A에서 출발해서 B까지 갈 수 있는 최단 경로는 몇 가지 일까요?
먼저 A에서 최단 경로로 직선으로 갈 수 있는 위치는 아래와 같고, 각각 반듯하게 가는 1가지 경우 밖에 없습니다.
그 다음 아래와 같이 A에서 C로 가는 경우를 생각하면 반듯하게 올 수 있는 이전 경로의 경우를 합한 2가지 입니다.
위 과정을 반복하면 A에서 B까지 가는 최단 경로는 총 35가지입니다.
과정이 앞에서 푼 분해합과 같은 방식으로 해결이 가능합니다.
다. 중복조합
이 문제를 또 다른 방법으로 접근할 수 있습니다.
A에서 B로 가려면 아래와 같이 각 층의 세로 경로 중에 반드시 단 하나만 지나가게 됩니다.
얼핏 보면 \( 5 \times 5 \times 5 = 5^3 \) 가지 같아 보이지만, 위에서 지나간 세로 경로보다 왼쪽에 있는 아래의 세로 경로는 지나갈 수 없습니다.
이렇게 생각해보면 1 ~ 5 중 중복을 허용하여 3가지의 조합을 구하는 문제와 같습니다.
예를 들어, (1, 1, 4), (1, 4, 1), (4, 1, 1)은 조합이기 때문에 다 같은 한 가지 경우이며, 경로로 그려보면 다음과 같습니다.
5가지 중에서 중복을 허용하여 3개를 고르는 조합을 중복조합이라고 부르며, \( \sideset{_5}{_3} {\rm H}\) 으로 표기합니다.
조합의 경우 순열에서 순서만 다른 경우를 제외하면 되는데, 중복조합은 어떻게 구할까요?
다 똑같이 생긴 공과 선택해야하는 가지 수를 나누어 주는 칸막이를 가지고 이해하면 쉽게 이해할 수 있습니다.
위와 같이 5가지 중에 3개를 고르는 경우, 5가지를 나누는 칸막이가 4개가 필요하고, 3개를 골라야 하므로 공 3개를 준비합니다.
그리고 순열을 구하면 되는데, 아래와 같이 공, 공, 칸, 칸, 칸, 공, 칸으로 세운 경우를 생각해봅시다.
칸 네 개가 1 ~ 5의 다섯 가지를 구분하고, 공 3개는 그 중 어느 것을 선택했는지를 의미합니다.
따라서 위와 같이 정렬한 경우에는, (1, 1, 4)를 의미하게 됩니다.
이렇게 모든 경우를 찾아보면,
위와 같이 35가지가 나옵니다.
다시 말해, \( \sideset{_5}{_3} {\rm H} = \cfrac{(3 + 5 - 1)!}{3! (5 -1)!}\) 입니다.
일반화 해보면, \( \sideset{_n}{_r} {\rm H} = \cfrac{(r + n - 1)!}{r! (n-1)!} \) = \(\sideset{_{r+n-1}}{_r}{\rm C}\) 와 같이 정리할 수 있습니다.
처음의 분해합 문제의 정답을 N과 K로 정리해보면, \(\sideset{_{N+1}}{_{K-1}}{\rm H} = \cfrac{(N + K -1)}{N!(K-1)!}! = \sideset{_{N+K-1}}{_{N}}{\rm C}\) 입니다.
N과 K가 5와 3일 때, \(\sideset{_7}{_5}{\rm C} = 21\)로 바로 구할 수 있습니다.
라. 파스칼의 삼각형
이 과정은 파스칼의 삼각형 안에서도 찾을 수 있습니다.
