중복 조합 : 어떻게 ps에서 쓰일까요?

 가끔 ps에서 중복 조합이 등장하는데요. nHk는, 서로 다른 n개의 원소에서 중복을 허용해서, 순서에 상관 없이 k개를 뽑는 가짓수를 의미합니다. 예를 들자면, n = 2이고 k = 2라고 해 봅시다. 원소는 0, 1이라고 해 봅시다. 이 때, 중복을 허용하지 않으면, 2개 중에 2개를 뽑는 가짓수는 (0, 1) 이렇게 나올 거에요. 그런데, 중복을 허용하는 경우 (0, 0)도 가능하고 (0, 1)도 가능하고, (1, 1)도 가능합니다. 따라서, 3이 나옵니다.

 

 n = 2이고 k = 3인 경우는 어떤가요? 중복을 허용하는 경우, (0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1) 이렇게 4개가 나옵니다. 이것을 다른 문제로 변환해 봅시다. 우리는 0을 x개 뽑고, 1을 y개 뽑았습니다. 이 때 x와 y의 합이 3이 나와야 합니다.

 

 

 그 문제로 변환될 수 있지 않을까요? 그러면, 서로 다른 원소 3개가 있습니다. 중복을 허용해서 4개를 뽑는 문제는 어떤 문제로 변환될 수 있을까요?

 

 

 0을 x개 뽑고, 1을 y개 뽑고, 2를 z개 뽑았을 때, x+y+z = 4를 만족하는 (x,y,z) 쌍 갯수와 관련이 있지 않을까요? 단, 이 때 x와 y와 z는 0보다 크거나 같은 정수일 겁니다. 문제를 조금 더 와닿게 conversion을 했습니다.

 

 

---

 a+b+c = k인 쌍 (a, b, c)의 갯수를 구하세요. 단 a, b, c는 0보다 크거나 같은 자연수이다. 아니면 a, b, c가 0보다 큰 정수일 때, a+b+c = k인 쌍 (a, b, c)의 갯수를 구하세요. 이런 문제가 ps에는 간혹 가다가 보입니다. 먼저, a + b + c = 5이면서 a>0, b>0, c>0인 가짓수를 구해 봅시다.

 

 일단 5개의 칸을 그리고, 칸 사이에 막대기를 넣어봅시다. 칸이 5개 있으니까, 막대기는 4칸이 있어요.

 

 

 그런데 여기에서, 초록색으로 칠한 칸의 갯수는 a, 파란색으로 칠한 갯수는 b, 보라색으로 칠한 갯수를 c라고 했을 때, a+b+c = 5를 만족합니다. 그러한가요? 그런데 이 a, b, c값이 0보다 크려면, 같은 막대기를 선택하면 안 됩니다. 그리고, 4개의 막대기 중 2개를 선택해야 함을 알 수 있어요.

 

 즉, a+b+c = 5이면서, a, b, c가 1보다 크거나 같은 정수인 쌍 (a,b,c)의 갯수는 (5-1)C(3-1)인 셈입니다.

 

 

 그러면 a+b+c = 6이면서, a>0, b>0, c>0인 쌍 (a,b,c)의 가짓수는 어떻게 구하면 될까요? 마찬가지로 칸막이를 그려보면 5개가 나옵니다. 이 중 2개를 택하면 3개로 분할됩니다. 초록색, 하늘색, 보라색으로요. 그럴려면 5개의 막대기 중 2개를 택하면 되기 때문에 (6-1)C2 = 5C2가 됩니다.

 

 

---

 그러면, a+b+c = k인데, a, b, c가 0보다 크거나 같은 쌍 (a,b,c)의 갯수는 어떻게 구할까요?

 

 

 마찬가지로 칸막이를 그려놓을 건데요. 일단 이것은 2개가 필요합니다. 그런데, 이 경우 어떻게 들어가면 될까요?

 

 

 1번 칸과 2번 칸 사이에 칸막이가 2개 들어가면 됩니다. 그러면 a = 1, b = 1 c = 4인 경우에는 어떤가요?

 

 

 1번과 2번 칸 사이에, 그리고 2번과 3번 칸 사이에 들어가기만 하면 됩니다. 공통적인 것은, 어떻게 나누더라도, 칸은 6개이고, 칸막이는 2개라는 겁니다. 총 8개의 칸 중에서 2개의 칸막이가 들어갈 칸을 찾는 가짓수와 같아요.

 

 

  따라서, 8C2가 우리가 원하는 답이 됩니다. 그러면 일반화를 시켜서 a(1) + ... + a(n) = k이고 a(1), a(2), ... , a(n)이 모두 0보다 크거나 같은 쌍 (a(1), ... , a(n))의 갯수는 몇 개일까요?

 

 

 k개의 칸이 있어요. 그리고 n개로 분할해야 합니다. 그러면 필요한 칸막이의 갯수는 n-1개일 거에요.

 

 

 그러면 이 칸들 중에 n-1개는 칸막이로 선택해야 합니다. 즉 (n+k-1)C(n-1) = (n+k-1)C(k)개의 쌍이 나옵니다. 즉, n개의 원소 중, k개를 뽑는데, 중복을 허용하고 순서 상관없이 뽑는 가짓수는 (n+k-1)C(n-1)이 되는 셈입니다.

 

 

---

 백준 12938번, 곱으로 분해하기는 언뜻 보면 굉장히 어려워 보입니다. 그래서 제가 난이도를 골드1 ~ 플레5 정도로 주었습니다. 실제로, 단순하게 dp로 접근한다면 공간을 어떻게 쓸 지는 안 봐도 비디오입니다.

 

 

 문제에 주어진 수를 소인수 별로 봅시다. 예를 들어서, m값이 1500이라면, 다음과 같이 보는 겁니다. 이 수는 소인수 2를 2개, 3을 1개, 5를 3개 가지고 있습니다.

 

 

 그러면, 6을 꺼낼 수 있어요. 그러면 250을 또 어떻게 분해할 수 있을 거에요. 그러면 6은 2를 1개, 3을 1개 가집니다. 수 하나를 꺼내는 것을 행동 1이라고 해 봅시다. 그러면, 다음에 또 어떤 수를 꺼낼 수 있을까요? 250을 그대로 꺼낼 수도 있어요. 2 하나, 그리고 5 3개. 이렇게요.

 

 

 그렇지만 50, 그러니까 2 하나, 5 2개를 먼저 꺼낸 다음에, 2하나, 3하나 5 하나. 이렇게 30을 꺼낼 수도 있을 겁니다.

 

 

 그러면 이 경우는 어떤가요? 먼저 2 하나와 5 두개를 꺼냅니다. 다음에 2 하나를 꺼내고, 3 하나 5 하나를 꺼냅니다. 이렇게 하면 3번의 행동만에 1500을 만들 수 있어요.

 

 

 그러면 이걸 소인수별로 나눠서 생각해 봅시다. 이 상황에서 저는 1번째 행동에서 2를 하나 꺼내고, 2번째 행동에서 2를 또 하나 꺼내고, 3번째 행동에서 2를 0개 꺼냈습니다. 그런데, 이것이 3을 0번째에 몇 개 꺼내고, 1번째에 몇 개 꺼내고, 2번째에 몇 개 꺼내고에 영향을 미치나요?

 

 그렇지 않아요. 그렇기 때문에, 우리는 소인수 2가 총 k개 있고, 소인수 3이 k'개 있다고 합시다. 행동을 n번할 수 있을 때, a(1) + ... + a(n)이 k이면서, a(1), ..., a(n)이 0보다 크거나 같은, 쌍 (a(1), ... , a(n))의 가짓수와, b(1) + ... + b(n)의 값이 k' 이면서, b(1), ... , b(n)이 0보다 크거나 같은, 쌍 (b(1), ... , b(n))의 가짓수를 곱하면 되는 것입니다. 곱사건으로 처리할 수 있다는 의미입니다.

 

 

 보시면, ti는 어떠한 소인수의 갯수입니다. 그리고 우리는 행동을 n번 합니다. 즉, ti개의 칸이 있고, 이를 n개의 영역으로 분할을 해야 하는데 이 때 칸막이는 n-1개가 있어요. 따라서, ti+(n-1)개 중에 막대기가 들어갈 자리인 (n-1)을 택하는 가짓수를 구하고, ans에 계속 곱해 나간다는 것을 알 수 있어요.

 

 각각의 소인수별로 독립 사건으로 처리하시는 것을 주목하시면 쉽게 이해하실 수 있습니다.