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

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/PartitionedSol70.java

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