[문제해결을 위한 창의적 알고리즘] partitioned 2 (고급 p.68)
앞선 포스트에서는 본 문제에 대한 보다 직관적인 풀이를 적었습니다. 그러나 책의 해설이 보여주는 풀이도 나름 의미가 있고 이해하고 있는 편이 좋을 것 같다는 생각이 들어 여기에 적어보자 합니다.
책의 풀이를 보면
f(n, k) = k이하의 자연 수 합으로 n을 만들 수 있는 경우의 수
라고 되어 있는데, 예제 입력의 경우를 살펴보면 n=5일때, 5이하의 자연수 합으로 5를 만들 수 있는 경우의 수를 구하는 함수라고 보면 될 것 같습니다. (실제 출력은 경우의 수가 아니라 각 경우를 출력해야 한다는 점은 주의해야 겠지요.)
코드를 살펴 보겠습니다.
import java.util.Scanner;
public class PartitionedSol70 {
// 문제에서 30이하의 수라고 했으므로 30개의 정수 배열
public static int[] a = new int[30];
public static int cnt;
public static int min(int a, int b){
return a > b ? b : a;
}
public static void solve(int n, int k) {
// n이 0인 경우는 직전 호출에서 원하는 만큼의 숫자가 배열에 들어간 경우이므로 출력
if (n==0){
for (int i = 0; i < cnt; i++)
System.out.print(a[i]+" ");
System.out.println("");
return;
}
// n을 만들기 위해 가능한 조합을 배열에 넣음
for (int i = min(n,k); i >=1; i--){
a[cnt++]=i;
solve(n-i, i);
cnt--;
}
}
public static void main(String[] args) {
int n;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
sc.close();
// n,n으로 solve함수 호출
solve(n, n);
return;
}
}
Big O(n^2): n은 종이 숫자