[Programmers] 입문) 구슬을 나누는 경우의 수 (학습, 자료형, 수학, 해답 확인)

 

이번 문제는 2가지 문제점을 해결하지 못 하고 나의 무능력한 수학능력에 시간을 끌어버린 케이스이다.

문제 자체에서도 난이도가 있다고 판단하였는지 힌트까지 주었다.

 

1. 수학적 공식을 코드로 변경이 가능하도록 간략하게 만들지 않았다.
2. 자료형의 최대값을 생각하지 않는 안일함에 특정 테스트들을 통과하지 못했다.

 

우선 주어진 숫자가 21!(결과값 : 51,090,942,171,709,440,000)만되어도 ulong(최대값 : 18,446,744,073,709,551,615)으로도 표현할 수 없는 막대한 숫자가 되어버린다.

 

 

---

처음 시도

using System;

public class Solution {
    public int solution(int balls, int share) {
        ulong ballsLong = (ulong)balls;
        ulong shareLong = (ulong)share;
        return (int)((Factorial(ballsLong, (ulong)(balls - share))) / Factorial(shareLong));
    }
    
    private ulong Factorial(ulong number, ulong stop = 0) {
        if (number == 1 + stop) return number;
        return number * Factorial(number - 1, stop);
    }
}

 

우선 가장 처음에는 팩토리얼 부분을 재귀함수로 구현하고 힌트로 제공된 공식을 코드로 구현하였다.

 

문제는 아무리 자료형을 바꾸더라도 위 5가지 테스트가 항상 실패한다는 사실이었다.

실패 사유를 찾기위해 질문하기 페이지를 참고한 결과 20!이후의 수가 너무 커서 정수 자료형이 감당을 못한다는 사실을 인지했다.

 

가장 처음에는 int형으로 팩토리얼을 연산하고, long, ulong 순서로 변경해보았다.

그러니 실패 케이스의 개수가 절반 > 7개 > 5개으로 줄어들었다.

 

그래서 코드 자체가 문제가 아닌 자료형의 최대값을 알지 못 했던 나의 안일함이 문제였다고 깨달았다.

 

그런데 여기서 또다른 문제는 정수형 중 가장 큰 ulong, 그보다도 더욱 특별한 목적으로 만들어진 decimal까지도 30!과 같은 거대한 숫자는 엄두도 내지 못하는 것이다.

 

따로 숫자 단위를 끊어 연산하는 수고를 해야만 하는 것일까? 질문하기에 다른 분들이 사용하는 BigInteger라는 자료형을 사용해야하는 것일까 고민을 하다가 결국 검색을 통해 해답을 찾았다.

 

명칭	표현 가능 수
double	123,456,789,012,345,000,000,000,000,000,000,000,000,000,000,000,000,000,000
decimal	79,228,162,514,264,337,593,543,950,335
ulong	18,446,744,073,709,551,615
30!	265,252,859,812,191,058,636,308,480,000,000
22!	1,124,000,727,777,607,680,000
21!	51,090,942,171,709,440,000

 

---

1차 성공

using System;

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

 

위 코드는 다음 주소의 개발자분이 풀이해주신 방법을 그대로 사용했다.

https://ulmu0426.tistory.com/6

 

이분의 풀이를 보면 예로 보자

조합의 공식대로 5C3를 작성시 다음과 같다.
n! / (n - m)! * m!
= 5 * 4 * 3 * 2 * 1 / (2 * 1) * (3 * 2 * 1)

이때 분모의 2 * 1을 분자인 5!에서 제거하면 다음과 같아진다.
= 5 * 4 * 3 * / 3 * 2 * 1

 

위 예시에 따라 주어진 개수 n과 선택될 경우의 수 m의 분모와 분자의 개수가 동일해지고 (5 / 3) * (4 / 2) * (3 / 1)로 연산이 되도록 코드를 작성하셨다.

이때, 곱하기와 나누기를 동시에 처리하여 빠르고 너무 거대해지는 수를 미리 나누어버리는 발상도 하셨다.

 

 

---

2차 성공

using System;

public class Solution {
    public int solution(int balls, int share) => Convert.ToInt32(Factorial(balls, balls - share) / Factorial(share));

    private double Factorial(double number, int stop = 0) {
        if (number == 1 + stop) return number;
        return number * Factorial(number - 1, stop);
    }
}

 

해답을 검색으로 찾았다는 부분에서 찜찜함이 머무르던 시간에 다른 분들의 정답을 확인하다.

나와 같은 팩토리얼에 double형을 사용하여 정답을 맞추신 분을 확인했다.

 

이때 뒷통수를 맞는 느낌을 받았다.

double이라면 ulong보다 더 큰 수를 표현할 수 있구나?

 

이에 원래 작성했던 코드를 double형으로 바꾸었더니 바로 모든 테스트가 통과되었다.

 

https://www.youtube.com/watch?v=jHiEhEen7dw&t=1s&ab_channel=%EA%BC%BC%EC%88%98%ED%95%99