프로그래머스 - 구슬을 나누는 경우의 수(feat. 조합)

문제 살펴보기

주어진 구슬 중 n개를 꺼낸다고 할 때, 가능한 경우의 수를 세서 반환하는 문제이다.

 

---

 

생각하기

관련 공식이 주어져 있어서, 공식만 적용하면 해결될거라고 생각했지만... 큰 함정이 숨어있었다.

 

바로 자료형의 범위이다.

 

이 문제에서는 팩토리얼을 다룬다.

 

그러다 보니 숫자의 값이 순식간에 커져서, 숫자를 있는 그대로 다룰 경우 int 자료형은 물론이고, double 자료형으로도 감당이 되지 않는다.

 

(13! 에서 이미 int 자료형의 범위를 크게 뛰어넘고, 21! 까지 가면 long 자료형의 최대값의 5배보다도 큰 값을 가진다..)

 

아주 기본적이면서 중요한 개념인데, 몇 번 실행하고 오류화면을 본 후에야 떠올렸다....

 

 

문제를 푸는 방식은 크게 두 가지로 나눌 수 있을 것 같다.

 

---

1. BigInteger 클래스 사용하기

 

BigInteger는 int 배열을 이용해서 숫자를 다루는 클래스이다.

 

BigInteger로 다룰 수 있는 숫자의 범위는 무한대여서 아주아주 큰 숫자 또는 정말정말 작은 숫자를 다룰 때 사용된다.

 

대신 기본 자료형이 아닌 만큼 int, long, float, double에 비해 연산 속도가 느려 필요할 때만 사용하는 것이 좋겠다.

 

---

2. 조합 공식(nCm)을 활용하기

 

주어진 공식은 조합 공식이다... 너무 오랜만에 봐서 조합 공식을 복습했다.

 

우선 주어진 조합 공식은 다음과 같다. (m만 r로 바꿨다.)

 

 

이 식을 풀어서 정리하면 다음과 같이 정리된다.

잘 기억나지 않는다면 직접 숫자를 넣어보자! 나도 처음엔 기억이 안나서 숫자를 직접 넣어봤다...

 

 

예를 들어, 만약 n=10, m=4인 경우, 문제에서 주어진 공식에 집어넣으면

이렇게 된다. 이제 분모와 분자를 정리하면 다음과 같은 결과가 나온다.

 

 

 

이를 일반화하면

요렇게 된다.

 

 

TMI) nCm = nCn-m 규칙도 기억해두면 좋을 것 같다.

 

nCm = nCn-m 예시

 

아무튼 이러한 공식을 이용해서 문제를 풀면, BigInteger를 사용해야될 정도로 숫자가 커지기 전에 문제를 해결할 수 있다.

 

 

---

풀어보기1

BigInteger는 정말정말 필요할 때만 사용하고 싶어서, 조합 공식을 최대한 활용하는 방법으로 문제를 풀었다.

 

처음 푼 방식은 다음과 같다.

 

double 자료형의 변수 a를 선언했고, 공식의 연산 결과를 a에 저장했다.

 

코드 전문은 다음과 같다.

if(share == 1) return balls;
if(share == balls) return 1;

double a = 1;       

for(int i=balls; i>=1; i--){
    if(i>share) a *= i;
    if(i<=balls-share) a /= i;
}

int answer = (int)a;

return answer;

조합 공식과 같이 봤을 때, balls가 n, share가 r에 해당한다.

 

 

하지만 영 마음에 안들어서 다른 분들의 풀이를 봤다.

 

그 중 재귀함수를 이용해 깔끔하게 푼 풀이가 있어서 해당 풀이를 참고해서 다시 풀어보았다.

 

---

 

풀어보기2

share가 0이 될 때까지 반복되는 재귀함수이다..

if(share == 0) return 1;

long answer = solution(balls-1, share-1);
answer *= balls;
answer /= share;

return (int)answer;

 

 

 

 

조합의 공식이니 BigInteger니 하면서 장황하게 적었지만, 이 문제에서 가장 중요한 개념은 자료형의 표현 범위이다..

 

다음번에는 절대 잊어버리지 않아야겠다.