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

문제 설명

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

제한사항

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

입출력 예

입출력 예 설명

• 입출력 예 #1

서로 다른 구슬 3개 중 2개를 고르는 경우의 수는 3입니다.

• 입출력 예 #2

서로 다른 구슬 5개 중 3개를 고르는 경우의 수는 10입니다.
Hint
서로 다른 n개 중 m개를 뽑는 경우의 수 공식은 다음과 같습니다.

Solution

사실 어려운 문제는 아니다. Java로 PS 언어를 전환하려다 보니 쉬운 문제들 위주로 다시 풀고있었는데 어떤 방법으로 풀든 DP로 풀면 그만이지만, 쉽게 놓치는 개념에 대해 한번 되짚기 위해 글을 쓴다.

import java.math.BigInteger;

class Solution {
    public BigInteger solution(int balls, int share) {
        BigInteger[] DP = new BigInteger[31];
        DP[0] = new BigInteger("1");
        DP[1] = new BigInteger("1");

        for (int i = 2; i <= 30; i++) {
            DP[i] = DP[i - 1].multiply(new BigInteger(Integer.toString(i)));
        }

        return (DP[balls].divide(DP[balls - share].multiply(DP[share])));

    }
}

답은 참 심플하다. 이런 문제를 위해 굳이 재귀호출을 쓸 필요는 없다는 것을 우리는 너무나 잘 안다.
C++이었다면 8byte를 넘어가는 숫자를 위해 unsigned long 처리를 해줬으면 끝날 일이지만 현재 언어는 Java다.

BigInteger 객체를 활용해야했다. 처음에 이게 뭔 괴랄한 녀석인가 싶었지만 long 범위를 벗어나는 숫자 데이터에 대한 처리를 도와주는 고마운 객체였다.

문제는 일반적인 연산자가 통하지 않기 때문에 메소드로 제공하는 가감승제 연산자를 사용해야 한다. 그것만 조심하면 이 문제는 쉽게 해결된다.

어쨌거나 정해진 값에 대한 리턴 값이 고정되어있을 때 메모이제이션을 활용해서 획기적으로 프로그램의 속도를 줄일 수 있다는 것은 너무나 명확한 정답이니, 언어에 따른 리턴 타입을 어떻게 처리 해 주느냐에 따라 같은 알고리즘이라도 결과가 다르다는 걸 항상 명심해야 한다는 걸 깨닫게 해 주는 쉬운 문제였다.