[문제해결을 위한 창의적 알고리즘] partitioned (고급 p.68)

이 문제의 해설은 굉장히 직관적이지가 않아 내 나름대로의 방법으로 풀어 보았다. 그림 설명과 결과값 출력이 조금 헛갈리게 설명되어 있으나, 출력 결과 값을 보면 주어진 n을 분할해서 내림차순 형태의 배열을 출력한다고 간단히 이해한 후 문제를 접근하는 편이 훨씬 낫지 않나 싶다.

import java.util.Scanner;

public class Partitioned {

public static int n;

//n은 30이하의 자연수라고 제한되어 ㅇ

public static int[] arr = new int[30];

// f는 k개의 정사각형 종이를 id번째의 배열에 몇개를 놓을 수 있는지를 계산

public static void f(int k, int id){

// k가 0, 즉 정사각형이 다 떨어졌다면 0부터 id번째까지 배열값 출력

if (k==0){

for (int i = 0; i <id; i++)

System.out.print(arr[i]+" ");

System.out.println("");

return;

}

// 높은 숫자부터 나와야 하므로 남은 k개부터 점차 종이를 줄여가면서 넣어본다

for (int i = k; i >= 1; i--) {

// 첫번째 배열값 (id==0)이라면 아무 숫자나 넣어도 괜찮다

if (id == 0)

arr[id] = i;

// 그외라면 앞 배열보다 같거나 작아야 넣을 수 있음

else if (arr[id-1] >= i)

arr[id]= i;

// 그도 저도 아니라면 다음 값을 넣어 봄

else

continue;

f(k-i, id+1);

}

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

f(n, 0);

sc.close();

return;

}

}

Big O(n^2): n은 종이 숫자 (최초 배열값을 n가지로 정해 본 후, 각 경우에 대해 종이가 다 떨어질때까지 해봐야 함)

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

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