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

 

 

Quiz

구슬을 나누는 경우의 수

 

 

Solution(Private)

 

팩토리얼 개념을 이해하고 풀어볼 수 있는 문제이다. 문제가 몇 번 틀리다가, JAVA에서 int는 범위가 정해진 타입임을 떠올리고, 처음부터 분모/분자를 나눠주는 식으로 문제를 풀게 되었다. 여기서 포인트를 다음처럼 생각했다.

 

[예 : 5개의 공이 있는데, 3개를 가져가는 케이스는?]

 

(분자) 5 * 4 * 3 * 2 * 1

(분모) (3 * 2 * 1) * (1 * 2) 

 

여기서 3이란 숫자를 기준으로 하여 공통된 숫자를 지우면, 

 

(분자) 5 * 4

(분모) 1 * 2 이 남게 된다!

 

따라서 for문을 이용하여 기준점까지 진행될 수 있도록 하였다.

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

 

추가로, 여기서 팩토리얼의 특징인

- n개의 서로 다른 원소 중 r개를 고를 때, nCr= (n−1)Cr + (n−1)C(r−1) 의 식을 이용해도 된다.