[Programmers] 최고의 집합 - Java

https://school.programmers.co.kr/learn/courses/30/lessons/12938

프로그래머스

---

1. 문제

합과 부분집합 개수가 주어질 때, 최고의 집합을 반환한다.

최고의 집합 조건은 원소들의 곱이 최대가 될 때이다.

 

2. 풀이

처음엔 바로 부분집합 or 조합이겠거니 하고 접근했다.

하지만 풀이가 복잡했고 다른 접근 방법이 있을 것 같아 블로그를 참고했는데

수학으로 푼 풀이가 많았다. 참고해서 나도 수학으로 풀어보았다.

 

1. 우선 개수가 합보다 크면 1끼리의 합 보다도 크게 되므로 -1을 return 해주고 시작한다.

2. 핵심은 bottom-up 방식이다.

- 합에서 개수를 나누면 해당 자리에 올 수 있는 가장 큰 값을 구할 수 있다.

- 합에서 그 값을 빼주고, 개수도 하나 줄어들었으니 빼준 후

다시 합에서 개수를 나누면 또 그 다음 자리에 올 수 있는 가장 큰 값을 구할 수 있다. 이것의 반복이다.

반복문은 최대 n번(최초 n) 돌게 된다.

3. 주의할 점은 for문에서 n의 값은 변하기 때문에 범위의 최대값으로는 ans.length로 개수를 설정했다.

 

3. 코드

class Solution {
    
    public int[] solution(int n, int s) {
        if (n > s) return new int[] {-1};
        int[] ans = new int[n];
        for (int i=0; i<ans.length; i++) {
            ans[i] = s/n;
            s -= s/n;
            n--;
        }
        return ans;
    }
}

4. 사담

여러 방향으로 접근해보자