[백준] 17213 과일 서리 JavaScript

혅·2024년 7월 31일

백준, 프로그래머스 -JavaScript-

목록 보기

126/215

문제

민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. 지환이는 완벽한 범죄를 위하여 처음 생각한 개수 만큼만 훔치려고 한다. 이때 지환이가 훔칠 수 있는 경우의 수가 몇가지나 될 지 알아보자. 단, 모든 종류의 과일을 적어도 1개는 훔친다.

입력

첫째 줄에 과일의 종류 수 N(1 ≤ N ≤ 10)이 주어진다.

둘째 줄에 훔치려 하는 과일의 개수 M(N ≤ M ≤ 30)이 주어진다.

출력

첫째 줄에 훔칠 수 있는 경우의 수를 출력한다.

예제 입력

3
10

예제 출력

내가 했던 풀이 방법

해당 문제는 중복 조합을 알고 풀어야 합니다. 이에 대해서는 중복 조합 <- 링크를 참고하여 풀이하였습니다.

간단하게 설명하면, 중복 조합은 "중복을 포함하여 뽑을 수 있는 경우의 수"를 의미한다.
즉, 한 번 뽑는다고 해서 다시 뽑을 수 없지 않다는 것이다.

중복 조합은 C가 아닌 H로 쓰며, nHr일 경우에 n개의 종류에서 중복을 포함하여 r개를 선택하는 조합의 갯수를 의미한다.
중복 조합은 아래와 같이 조합으로 풀이를 할 수 있다.

여기서 문제에서는 모든 종류의 과일을 1개 이상은 서리해야 한다고 했는데 이는 따로 신경 쓸 필요가 없다. 왜냐하면, 과일이 A, B, C가 있다고 한다면 조합 중에 A, B, C는 이미 존재한다고 생각하면 되기 때문이다. 서리해야 하는 과일의 갯수에서 과일의 종류만큼을 제외한 값만큼 중복을 포함해서 선택하면 되는 것이다.

즉 N개의 종류에서 M-N개만큼 중복을 포함하여 선택하는 경우의 수를 생각하면 된다.
이를 공식에 대입하게 되면, N+M-N-1CN-1이므로 정리하면 M-1CN-1을 계산하면 된다.

코드

const fs = require('fs');
const input = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let N = Number(input[0]);
let M = Number(input[1]);

function combination(n, r) {
  if (r > n) return 0;
  if (r === 0 || r === n) return 1;
  r = Math.min(r, n - r);

  let c = 1;
  for (let i = 0; i < r; i++) {
    c = (c * (n - i)) / (i + 1);
  }
  return c;
}

console.log(combination(M - 1, N - 1));