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

https://school.programmers.co.kr/learn/courses/30/lessons/120840

프로그래머스

문제)머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.

 

 

 

 

 

 

풀이)

class Solution {
    public int solution(int balls, int share) {
        long answer = 1;
        int idx = 1;
        for(int i = share+1; i<= balls; i++){
            answer *= i;
            answer /= idx++;
        }
        return (int)answer;
    }
}

처음에 그냥 다 int형으로 두었을때 30C3이럴경우 값이 30!처리과정에서 int값을 넘게 되고, long형도 초과하게 되어서 BigInteger를 사용해야 될 것 같아서 그거 말고 찾은 방법이다.

mCn = m! / n!*(m-n!) 이니까, 일단 처리를 위해 answer형은 long형으로 받고

m! / n!*(m-n!)이 식에서 어차피 분자 m!이 진행되는동안 1~n!의 값은 어차피 분모의 n!로 인해서 사라질 꺼니까 그냥 n에서 1을 더한값부터만 나는 곱하면 된다. 이 곱한 answer에서 m-n!을 또 나눠줘야 한다. share+1부터 balls까지는 어차피 balls-share와 같기 때문에 for문을 한번 돌때마다. idx를 1씩 더해가며 나누면, (m-n)!과 동일한 계산결과를 도출할 수 있다.

 

진짜 자료형 때문에 아주 헷갈리는 문제같다...ㅜㅜ