2023.08.18 - [➜ 코딩 테스트/프로그래머스] - 프로그래머스 - 구슬을 나누는 경우의 수 (JAVA)
프로그래머스 - 구슬을 나누는 경우의 수 (JAVA)
class Solution { public static int solution(int balls, int share) { int answer = 0; answer = factorial(balls, share); return answer; } public static int factorial(int n , int m){ if( m == 0 || n == m){ return 1; }else{ return factorial(n -1 , m - 1) + fact
mangseok.tistory.com
문득 이 문제를 푸는 와중 재귀를 활용하는데 조합과 파스칼의 삼각형의 원리에 기반해 문제를 푸는 것이였다.
그래서 조합과 파스칼의 삼각형에는 무슨 관계가 있고 어떤 원리로 조합이 풀리게 되는건지 알아보게 되었다.
조합이란?
조합이란, 주어진 집합에서 일부 원소를 선택하는 모든 방법을 의미한다. 순서를 고려하지 않는 선택 방법을 의미하는데, 수학적으로 n개의 원소 중에서 k 개를 선택하는 조합의 수는 이렇게 보여진다
파스칼의 삼각형 (Pascal's Triangle)
파스칼의 삼각형은 숫자 배열로 삼각형 모양으로 보여진다. 첫 번째 행부터 시작해서 각 행의 양 끝의 숫자는 항상 1 이며, 그 사이의 숫자는
바로 위 행의 인접한 두 숫자의 합으로 구성된다.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
조합과 파스칼의 삼각형의 관계
파스칼의 삼각형의 각 숫자는 조합으로 표현될 수 있다.
예시로 파스칼의 삼각형이 n번째 행의 k번째 숫자는 C(n,k)와 동일하다
1 => C(0,0)
1 1 => C(1,0) C(1,1)
1 2 1 => C(2,0) C(2,1) C(2,2)이런식으로 진행된다.
조합의 성질 중 하나인
