구슬을 나누는 경우의 수
살려줘
서로 다른 n개중에서 m개를 뽑는 경우의 수 구하기
조합, 파스칼 삼각형
🎯 문제
머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.
<제한사항>
1 ≤ balls ≤ 30
1 ≤ share ≤ 30
구슬을 고르는 순서는 고려하지 않습니다.
share ≤ balls| balls | share | result |
|---|---|---|
| 3 | 2 | 3 |
| 5 | 3 | 10 |
⛳ 답안
class Solution {
public int solution(int balls, int share) {
int answer = 0;
answer=key(balls, share);
return answer;
}
// 서로 다른 n개중에 m개 뽑는 경우의 수
public static int key(int balls, int share) {
// 0개를 뽑거나 전체를 뽑는 경우의 수는 무조건 1개
// 이거 안하면 재귀함수 못끝나
if(share==0 || share==balls) {return 1;}
// 조합을 파스칼 삼각형 안에 결과값으로 풀기
else {
return key(balls-1,share-1) + key(balls-1, share);
}
}
}
🎲 과정
진짜 너무 어려워...여기저기 힌트 다얻으면서 이해만 겨우겨우 했다
그 이해도 완벽하진 못해...어떤 원리로 되는지 알았어
일단 새롭게 알게 된 것부터 정리
이런 재귀함수 문제 한 7개 정도만 더 풀어보면 조금더 이해할 수 있겠다 싶을 정도로는 이해했어
-
조합
서로 다른 n개 중에서 r개를 고르는 경우의 수 , 이때 뽑는 순서가 중요하지 않으면 조합!
순서가 중요하면 순열! -
파스칼 삼각형
조합의 수를 삼각형 모양으로 배열한 것.
조합에 대한 결과값을 삼각형 안에 숫자로 계산할 수 있는 규칙같은건가봐
맨 처음 세로줄은 한개도 선택하지 않은 경우의 수 , 따라서 모두 1 (아무것도 선택하지 않는게 1개의 경우래...문과는 이해못하겠는 문법이야...)
맨 마지막 세로줄은 모두 선택하는 경우의 수
첫번째줄부터 0으로 세는거기 때문에 5개 중에 3개를 선택하는 경우면 세로 6번째에 가로 4번째 줄 보면 된다
암튼 윗 줄의 양옆의 수를 더하면 내가 구하고자 하는 값의 결과값이 나온대
그니까 5,3을 구하고 싶으면 4,2 와 4,3 의 결과값을 더하면 되고
4,2의 값을 알려면 또 3,1 과 3,2의 결과값을 더하면 된대
이걸 재귀함수로 풀면 되는 건가봐
- 재귀함수
재귀함수 알고있다고 생각했는데 전혀 모르는 거였나봐
나는 그냥 본인 자신을 계속 호출시키는 함수라고 알고 있기만 했는데
이 함수의 return값을 어떻게 하겠다는 생각은 전혀 못했어...
이거 return 이해하는게 너무 힘들었어...
아직도 완전히 이해는 못한듯
재귀함수란
함수 내에서 자기 자신을 계속적으로 요청하는 함수
함수가 콜 되면서 최근에 자신을 부른 원래 함수가 스택에 차곡차곡 쌓이게 된다.
맨 처음 불린 함수는 맨 아래에 쌓이게 됨
스택 맨위에 있는 함수가 return값이 나오고 종료되면 점점 밑으로 하나씩 내려오게 되는 구조인 것 같다.
처음 불려진 함수에서(스택 맨 밑에있는 메소드) return 되는 값이 최종 return 값이 된다
이 글이 진짜 이해 잘됐어 참고하기!
https://marobiana.tistory.com/79
참고참고!!!
그니까 재귀함수가 실행되면 호출이 먼저 쫙 되고 종료가 안된채로 스택에 쌓여있다가 자신을 다시 콜하지 않는 return이 나오면 함수가 종료되면서 스택에 쌓여있는 전에 호출된 함수들을 다시 실행시키는 구조
그래서 본인 자신을 부르지 않는 return값이 하나는 있어야되나봐
위에 풀때 한개도 선택하지 않는 경우의 수 와 전부 선택한 경우의 수에 대한 return 1 값을 안주면 오류났었어
암튼 그렇게 풀면 스택 맨 아래에 있는 함수의 return 값이 최종적으로 반환된다.
