문제
민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. 지환이는 완벽한 범죄를 위하여 처음 생각한 개수 만큼만 훔치려고 한다. 이때 지환이가 훔칠 수 있는 경우의 수가 몇가지나 될 지 알아보자. 단, 모든 종류의 과일을 적어도 1개는 훔친다.
입력
첫째 줄에 과일의 종류 수 N(1 ≤ N ≤ 10)이 주어진다.
둘째 줄에 훔치려 하는 과일의 개수 M(N ≤ M ≤ 30)이 주어진다.
출력
첫째 줄에 훔칠 수 있는 경우의 수를 출력한다.
예제 입력
3
10예제 출력
36풀이에 사용할 알고리즘 구상
먼저 문제에서 주어진 예제를 바탕으로 어떻게 문제를 해결할 지 생각해보자.
지환이는 3가지 종류의 과일을 적어도 한 개 이상 훔쳐서 과일을 총 10개 훔치게 된다. 이 때 훔칠 수 있는 경우의 수를 출력하면 된다.
여기서 중요한 점은 모든 종류의 과일을 적어도 한 개 이상 훔친다는 점이다. 따라서 과일을 훔치는 모든 경우에서 모든 종류의 과일이 최소 1개는 존재한다.
위의 예제를 살펴보면 결국 이 예제는 3가지 종류의 과일을 10개 훔치는 경우의 수를 구하는 게 아니고, 3가지 종류의 과일을 7개 훔치는 경우의 수를 구하는 예제가 된다. 모든 과일을 적어도 한 개 이상 훔쳐야 하기 때문에 과일 3가지는 무조건 한 가지 경우로 고정되기 때문이다.
따라서 이 문제에선 N가지 종류의 과일 M개를 훔치는 경우의 수 대신, N가지 종류의 과일 (M-N)개를 훔치는 경우의 수를 구하면 된다.
그리고 이 경우의 수를 구하려면, 서로 다른 과일 (M-N)개를 선택할 때 각각 N가지의 종류 중에서 선택하는 경우이기 때문에 조합을 사용해야 한다. 다만 이 때 과일 종류를 고를 때 중복을 허용하고 순서를 고려하지 않기 때문에 중복조합을 사용한다.
조합과 중복조합의 공식은 다음과 같다.
결국 이 문제는 이 조합 공식을 코드로 어떻게 잘 옮기는지가 키 포인트가 된다.
나는 분자와 분모를 각각 변수로 두고 이를 계산하여 나누는 함수를 하나 만드는 방식으로 풀었다.
앞서 언급한 대로 N가지 종류의 과일 (M-N)개를 훔치는 경우의 수를 중복조합으로 구하는 방법이기 때문에
를 계산한 결과를 출력하면 된다.
제출 코드
// 2020년 8월 작성한 C++ 코드
#include <iostream>
using namespace std;
long long comp(long long a, long long b){
if (a == 0) return 1;
if (b == 0) return 1;
if (a == 1) return 1;
if (b == 1) return a;
long long cut1 = a - b + 1;
long long cut2 = a - b;
long long boonja = a;
long long boonmo = 1;
long long c = 1;
while (true){
a--;
c++;
boonja *= a;
boonmo *= c;
if (a == cut1) break;
if (c == cut2) break;
}
return boonja/boonmo;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int N, M; cin >> N >> M;
cout << comp(M-1, M-N);
return 0;
}반년쯤 지난 뒤 문제를 다시 풀어봤다. 조합을 재귀 형식으로 구현하면 코드를 훨씬 간결하게 고칠 수 있다.
// 2021년 2월 작성한 Java 코드
import java.io.*;
public class Main {
static int combination(int n, int r) {
if (r == 0 || n == r) return 1;
return combination(n-1,r-1) + combination(n-1,r);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
m -= n;
System.out.println(combination(n+m-1, m));
}
}
회고 (2020년 8월 기준)
내가 짠 조합 함수의 경우 연산 중에 int 타입의 범위를 벗어나는 경우가 있어서 부득이하게 변수 타입을 long long 타입으로 지정했다. 게다가 예외처리를 하느라고 코드가 엄청 길어지고 보기 더러워졌다. 문제를 다 풀고 난 뒤 구글링하여 다른 풀이를 살펴보니 조합을 코딩할 때 훨씬 더 간결하게 작성하는 방법이 있었다. 또한 중복조합 대신 브루트 포스 알고리즘이나 DFS 알고리즘, 그리고 재귀함수를 사용하여 푸는 방법도 있었다.
