[문제해결을 위한 창의적 알고리즘] 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 

문제해결을 위한 창의적 알고리즘 목록