[프로그래머스 - 자바] 구슬을 나누는 경우의 수

 

정답

 

class Solution {

public int solution(int balls, int share) {

long answer = 1;

int shareIndex = 1;

for(int i = share+1; i <= balls; i++){

answer *= i;

answer /= shareIndex;

shareIndex++;

}

 

return (int)answer;

}

}

 

 

풀이 

 

 

분자 : n * n-1 * n-2 * n-3 ······ 3 * 2 * 1
분모 : (n-m* n-m-1 ······ 2 * 1) * (m* m-1 * m-2 * ······ * 2 * 1)

여기서 m은 반드시 n보다 작다.
그러므로 분모에 있는 m!은 분자에 있는 n!으로 소거될 수 있다

예를 들어 n이 5, m이 3이라면
분자는 : 5 * 4 * 3 * 2 * 1
분모는 : (2 * 1) * (3 * 2 * 1)
이 된다.
여기서 (3 * 2 * 1) 분모를 분자의 3 * 2 * 1로 나누어 소거 가능하다