[문제해결을 위한 창의적 알고리즘] Combination (고급, p29)
이 문제는 점화식 유도를 연습하기에 매우 좋은 문제라는 생각이 든다. n개 중에서 k를 고를 때, n개 중에서 k-1개를 고르는 것과 어떤 관계가 있을 지를 생각해 보면 쉽게 점화식을 유도할 수 있다. 또한 교재에서 곱하기를 먼저 다하고 나누기를 하는 것 보다는 나누기를 먼저하고 곱하기를 하는 것이 overflow가 발생하지 않도록 한다는 팁도 유용해 보인다.
import java.util.Scanner;
public class Combination {
// n개 중에서 선택 (1<=n<30)
public static int n;
// k개를 선택 (1<=k<30)
public static int k;
public static int f(int a) {
// 선택할 k가 1이면 n 반환
if (a==1)
return n;
// n과 k가 같다면 1 반환
if (a==n)
return 1;
// 그외 경우는 관계식에 따라 계산
return (n-a+1)/a*f(a-1);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
sc.close();
System.out.println(f(k));
return;
}
}
Big O(n): (n은 k)
GitHub: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/Combination.java