[알고리즘문제풀기] 구슬을 나누는 경우의 수

silver

Jan 23, 2025

Contents

문제 내가 작성한 오답 내가 작성한 정답 다른 사람들의 정답

문제

school.programmers.co.kr

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

내가 작성한 오답

: 정수 연산의 오버플로우 → int로는 안된다


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

: for문내에서 곱셈과 나눗셈을 동시에 하여 int 범위 내로 가져오려했으나 그래도 초과하는 예시가 존재했다


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

내가 작성한 정답

: answer를 long으로 정의하고 마지막에 리턴 시 형변환 해줬다


class Solution {
    public int solution(int balls, int share) {
        long answer = 1;

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

다른 사람들의 정답


class Solution {
    public long solution(int balls, int share) {
		    // C(n, r) = C(n, n-r) 이므로, 작은 값으로 변환하여 계산량을 줄임
        share = Math.min(balls - share, share);

				// C(n, 0) = 1 이므로, 재귀 종료 조건
        if (share == 0)
            return 1;

				// 	C(n, r) = C(n-1, r-1) * (n / r)
        long result = solution(balls - 1, share - 1);
        result *= balls;
        result /= share;

        return result;
    }
}

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

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

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

class Solution { public long solution(int balls, int share) { // C(n, r) = C(n, n-r) 이므로, 작은 값으로 변환하여 계산량을 줄임 share = Math.min(balls - share, share); // C(n, 0) = 1 이므로, 재귀 종료 조건 if (share == 0) return 1; // C(n, r) = C(n-1, r-1) * (n / r) long result = solution(balls - 1, share - 1); result *= balls; result /= share; return result; } }