반응형
구슬을 나누는 경우의 수 (JAVA)
프로그래머스 문제 보러가기 👉🏻
내가 풀었던 풀이법 보러가기 👉🏻
1. 문제 분석
우선 이 문제는 조합 과 관련된 문제이다. 수학을 너무 오래전에 한 나는 너무 어려웠다..ㅎ.....
두번째로 문제를 볼 때에는 힌트에 초점을 맞추었다.
첫번째에 문제를 풀 때 다른 사람들의 코드를 너무 많이봐서 내 손으로 직접 푼 것 같지 않았다.
우선 n!/(n-m)!*m! 식을 해석해보려고 한다.
n! 는 만약 n=3라고 가정할 때 n*(n-1) 즉 3*2*1로 생각하면 된다.
(n-m)!*m은 m=2라고 가정할 때 (1*1)*2로 된다.
그러면 약분이 되어서 최종값 3 이 된다.
2. 방법
처음에 이용했던 Combination에 대해서 알아보았다.
Combination 함수는 집합을 순서가 없이 선택하는 것을 말한다.
*** 위의 식을 공식화하면 nCr = (n-1)Cr + (n-1)C(r-1) 이다.
나는 해당 식을 적용하여 재귀함수를 통해서 구현해야한다 생각했다. (재귀함수에 대해서는 차차 더 공부가 필요하다고 느꼈다..)
그렇다면 경우의 수를 따져보면,
공의 개수 == 뽑을 공의 개수
뽑을 공의 개수 == 0 일 경우에는 경우의 수가 1이므로 1을 반환하고 그 외에는 위의 식을 이용하여 반환하면 된다.
class Solution {
public int solution(int balls, int share) {
return combination(balls, share);
}
public static int combination(int balls, int share) {
if (balls == share || share == 0) return 1;
return combination((balls - 1), (share - 1)) + combination(balls - 1, share);
}
}
3. 느낀점
- 아직 너무 많이 부족하다.
- 재귀함수랑 기본 개념에 대해서 탄탄하게 잡고 가야할 것 같다.
- 많은 문제를 많이 풀면서 익히는게 좋을 것 같기도 하다.
반응형
'알고리즘 > 프로그래머스:LV00' 카테고리의 다른 글
[LV00] 배열 회전시키기 (0) | 2023.06.19 |
---|---|
[LV00] 공 던지기 (1) | 2023.06.19 |
[LV00] 구슬을 나누는 경우의 수 (0) | 2023.05.09 |
[LV00] 가위 바위 보 (0) | 2023.05.08 |
[LV00] 모스부호 (1) | 2023.04.27 |