프로그래머스

프로그래머스 구슬을 나누는 경우의 수 문제풀이

애용이랑떼껄룩 2024. 2. 20. 10:39
728x90

문제 설명

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

제한 사항

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

입출력 예

balls share result
3 2 3
5 3 10

문제 풀이

public int solution(int balls, int share) {
    return combination(balls, share);
}

public int combination(int balls, int share) {
    if(balls == share || share == 0) return 1;
    else return combination(balls - 1, share - 1) + combination(balls -1 , share);
}

 

해당문제도 풀다 풀다 안 돼서 다른 사람 풀이를 참고하였는데 재귀함수를 사용하였다.

재귀함수에 대해 간단한 예제와 설명을 적어놓았으니 궁금하신 분은 https://mini0726.tistory.com/27 통해 확인!

위 문제의 combination은 경우의 수 공식인 팩토리얼을 사용한 것인데

잠깐! 팩토리얼이란?

서로 다른 n개를 나열하는 경우의 수를 의미한다. n부터 1씩 줄여나가면서 1이 될 때까지의 모든 수를 다 곱하면 된다.

 

서로 다른 n개중에 r개를 선택하는 경우의 수 를 구하는 문제로 조합(nCr)이라고 한다.

입출력 예처럼 3,2를 입력하였다고 하면

첫 번째 return은 combination(2, 1) + combination(2, 2) 이 된다.

그 후 앞에 있는 combination(2, 1)에 대한 호출을 다시 한번 실행한다.

그럼 (combination(1, 0) + combination(1, 1)) 이 되는데 share가 0 이거나 balls와 값이 같으면 1을 호출하므로  2가 나온다.

그런 후 처음에 3,2를 실행했을 때 남아있던 combination(2, 2)를 실행하여 해당 return값도 1

즉 (combination(1, 0) + combination(1, 1)) + combination(2, 2) = 1+1+1 해서 결괏값이 3이 나온다.

 

combination(3, 2) = combination(2, 1) + combination(2, 2)
                  = (combination(1, 0) + combination(1, 1)) + (1)

combination(1, 0) = 1
combination(1, 1) = 1
combination(3, 2) = (1 + 1) + 1
	          = 3
 
 

 

해당문제는 수학공식도 알아야 하고 이해하기도 꽤 힘들어서 애먹었다..ㅠ

 

태클은 환영!

 

 

반응형