최고의 집합

자연수 N개로 이루어진 집합 중에, 각 원소의 합이 S가 되는 수의 집합은 여러 가지가 존재합니다. 최고의 집합은, 위의 조건을 만족하는 집합 중 각 원소의 곱이 최대가 되는 집합을 의미합니다. 집합 원소의 개수 n과 원소들의 합 s가 주어지면, 최고의 집합을 찾아 원소를 오름차순으로 반환해주는 bestSet 함수를 만들어 보세요. 만약 조건을 만족하는 집합이 없을 때는 배열 맨 앞에 –1을 담아 반환하면 됩니다. 예를 들어 n=3, s=13이면 [4,4,5]가 반환됩니다.
(자바는 집합이 없는 경우 크기가 1인 배열에 -1을 담아 반환해주세요.)

주요 로직은 "합이 S가 되는 집합의 경우"를 구하는 것이기 때문에 bfs로 쉽게 구현할 수 있다. 다만 집합의 길이가 가변적이기 때문에 단순히 값을 집어넣지 않고 메소드를 한번 통과해야하는 번거로움이 있었다.

이런 문제는 알고리즘 강의를 듣기 전에는 풀 수 없었을 문제 유형이다. bfs를 사용하여 문제를 푼다는 지식이 없었기 때문이다. 비록 bfs가 최적의 풀이는 아닐 지라도 잘 공부 했다는 생각이 들어서 기분은 좋았다.

import java.util.Arrays; //테스트로 출력해 보기 위한 코드입니다.
import java.util.LinkedList;
import java.util.Queue;
 
public class BestSet {
 
    public int[] nextSet(int[] arr, int n) {
        arr[n] += 1;
        return arr;
    }
 
    public int sum(int[] arr) {
        int result = arr[0];
        for (int i = 1; i < arr.length; i++) {
            result += arr[i];
        }
        return result;
    }
 
    public int multiple(int[] arr) {
        int result = arr[0];
        for (int i = 1; i < arr.length; i++) {
            result *= arr[i];
        }
        return result;
    }
 
    public int[] bestSet(int n, int s) {
        int[] answer = new int[n];
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < answer.length; i++) {
            answer[i] = 0;
        }
        q.add(answer);
 
        while (!q.isEmpty()) {
            int[] temp = q.remove();
 
            if (sum(temp) == s) {
                if (multiple(temp) >= multiple(answer)) {
                    System.arraycopy(temp, 0, answer, 0, temp.length);
                }
                continue;
            } else if (sum(temp) > s) {
                continue;
            }
            
            for (int i = 0; i < n; i++) {
                if (sum(temp) < s) {
                    q.add(nextSet(temp, i));
                }
            }
        }
        
        if(answer.length == 0) {
            answer = new int[1];
            answer[0] = -1;
        }
        
        Arrays.sort(answer);
 
        return answer;
    }
 
    public static void main(String[] args) {
        BestSet c = new BestSet();
        // 아래는 테스트로 출력해 보기 위한 코드입니다.
        System.out.println(Arrays.toString(c.bestSet(3, 13)));
    }
 
}