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

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

처음에는 아래와 같이 풀었다. 하지만, 이렇게 풀면 오버플로우가 발생해 일부 테스트 케이스를 통과하지 못하는 경우가 발생하였다. 이것을 방지하기 위해 중간중간 나누는 로직을 추가하여 int형의 크기 초과를 하지 않도록 해 주었다.

초기 코드

class Solution {
    public int solution(int balls, int share) {
        //balls : 갖고 있는 구슬 개수 -> n
        //share : 나누어 줄 구슬 개수 -> m
        int num = 1; //분자
        int den1 = 1; //분모 앞부분
        int den2 = 1; //분모 뒷부분
        for(int i=balls; i>0; i--){
            num = num * i;
        }
        
        for(int i=(balls-share); i>0; i--){
            den1 = den1 * i;
        }
        for(int i=share; i>0; i--){
            den2 = den2 * i;
        }
        
        int answer = 0;
        answer = num / (den1 * den2);
        return answer;
    }
}

정답 코드

인터넷 검색을 통해 풀었다.. 이건 처음부터 내 머리로 생각해 내기 쉽지 않은 듯 보인다...ㅎㅎ 이번 기회에 잘 이해해 보도록 해야겠다.

우선, for문이 왜 저렇게 나오는지가 이해가 안가서 직접 balls가 5, share가 3일때를 그려보았다.

분자의 경우는 balls부터 share까지만 곱한 것이고, 분모의 경우는 share부터 1까지 곱한 것이다. 이를 for문에서 나타내면 아래 식처럼 나오는 것이다.

이 때, answer를 long으로 설정해 주어야 모든 테스트 케이스를 통과한다.

class Solution {
    public long solution(int balls, int share) { 
        long answer = 1;

        for(int i = 0; i < share; i++){
            answer = answer * (balls - i) / (i + 1);
        }
        return answer;
    }
}