구슬을 나누는 경우의 수_programmers_lev00

<코딩 테스트>

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

<나의 풀이 과정>

만약 balls 이 5개라고 하고,

share 가 3개라고 한다고 예시를 들자면,

(2x1x3x2x1)/(5x4x3x2x1)을 해주면 되는데

둘을 나눌때 2x1이 겹치니까 그부분은 빼고 나눠주는 방식으로 했습니다,

즉, (3x2x1) / (5x4x3)을 해주면 됩니다.

(balls-(share-1))

 

<나의 풀이 코드>

package com.programmers.level00.구슬을나누는수;

public class Test {

	public static void main(String[] args) {
		System.out.println(solution(5, 3));// 10
	}

	static int solution(int balls, int share) {
		double answer = 1;
		double dBalls = (double) balls;
		double dShare = (double) share;

		// 1. 쉐어를 해야하는 경우의 수 전까지 총 구슬의 수와 뺀 것을 곱한값 저장
		for (int i = 0; i < dShare; i++) {
			// i = 0,1,2
			answer *= dBalls - i;
			// answer = (5-0)*(5-1)*(5-2)
		}

		// 2. 쉐어를 해야하는 경우의 수 전까지 총 쉐어를 해야하는 수를 뺀 값을 answer와 나눔.
		for (int i = 0; i < dShare; i++) {
			// i = 0,1,2
			answer /= dShare - i;
			// 60/= (3-0)(3-1)(3-2)
			// 3 2 1
		}

		return (int) answer;
	}
}

<다른 사람 풀이>

class Solution {
    public long solution(int balls, int share) {
        share = Math.min(balls - share, share);

        if (share == 0)
            return 1;

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

        return result;
    }


}

<다른 사람 풀이>

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

        int d = (balls - share) > share ? share : balls - share;
        if (d == 0) return 1;

        return solution(balls - 1, d - 1) * balls / d;
    }

}

 

 

 

 

 

 

 

 

 

 

 

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

프로그래머스