[프로그래머스][Java][Lv. 3] 최고의 집합

문제 설명

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

 

---

 

제한 사항

 

---

입출력 예

 

---

 

풀이

class Solution {
    public int[] solution(int n, int s) {
        int[] answer = new int[n];
        int val = s / n;
        
        if (s % n == s) return new int[] { -1 };
        for (int i = 0; i < n; i++) {
            answer[i] = val;
            s -= val;
            if (s % (val + 1) == 0 && (val + 1) * (n - i - 1) == s) val++;
        }
        return answer;
    }
}

 

---

 

후기

가장 큰 곱을 구하는 방법은 큰 수끼리 골고루 분포하도록 하는 것이다.

예를 들어, 25를 4개로 나누면 6 6 6 7이 될 것이다. 기본적인 방향은 6 6 6 6으로 만들고 뒤에서부터 남는 1씩 더해주면 된다. 그런데 이렇게 했더니 효율성 테스트를 통과하지 못해서 (두 번 순회하기 때문인듯하다...) 한 번만 순회하는 로직으로 변경했다. 기본적으로 32와 n=5를 예로 들면, 6 6 6 7 7이 될 것이다. 일단 6을 저장하다가 남은 합이 7로 나눠질 것 같으면 그 때부터 7로 저장하기 시작하는 방법이다.