[프로그래머스(Java)] 구슬을 나누는 경우의 수 - 부동소숫점문제

 

Level. 0

 

문제

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

제한사항
1 ≤ balls ≤ 30
1 ≤ share ≤ 30
구슬을 고르는 순서는 고려하지 않습니다.
share ≤ balls

 

서로 다른 n개 중 m개를 뽑는 경우의 수 공식은 다음과 같습니다. 

 

 

풀이

class Solution {
    // 부동소수점 문제
    public int solution(int balls, int share) {
        long answer = 1;

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

    }
}

 

해결방법 - 프로그래머스 질문목록 참고

 

https://school.programmers.co.kr/questions/42602

프로그래머스

 

1. 공식사용

서로 다른 n개 중 m개를 뽑는 경우의 수 공식 = n!/ ((n-m)! * m!) 

즉, 15개의 공에서 3개를 꺼내는 경우는 아래와 같이 풀 수 있다. 

(15 * 14 * 13) / (1 * 2 * 3)

 

2. 오버플로우 발생

n! 의 경우 n 이 30이 되면, 30! 의 값이 Long타입으로 해결이 되지 않는 큰 숫자가 나온다.

따라서, 단계별로 계산하는 방법을 사용해야 한다. 

(15 / 1) * (14 / 2) * (13 / 3) 

 

3. 부동소숫점

13/3 의 경우 무한 소수이기 때문에 부동소수점문제가 발생한다.

위 문제를 해결하기 위해 기존 계산된 값에 분자를 먼저 곱한 후 분모를 나눠주는 방법을 사용한다.
n개의 연속된 정수에는 항상 n의 배수가 포함되는 것을 활용한 것이다. 

 

 

 

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/120840?language=java 

프로그래머스