[프로그래머스 Level 3] 최고의 집합 - JavaScript

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(n, s) {
    const quotient = Math.floor(s / n);
    const remainder = s - quotient * n;
    return quotient
        ? [...Array(n - remainder).fill(quotient), ...Array(remainder).fill(quotient + 1)]
        : [-1];
}

최고의 집합이 되려면 합이 S가 되는 수의 집합 중에서 집합의 각 원소의 곱이 최대가 되어야 한다. 이를 만족하려면 각 원소간의 차이가 최소가 되도록 하면 된다. (합이 일정할 때 곱이 최대가 되려면 각 수의 차이가 최소가 되어야 함)

(ex: 합이 10이 되는 두 수 중에서 곱이 최대가 되는 경우를 구할 때, 1 * 9, 2 * 8, 3 * 7, 4 * 6, 5 * 5를 모두 구해보면 각 원소의 차가 작아질수록 곱이 커짐을 알 수 있다.)

 

각 원소의 차이가 최소가 되게 하기 위해서 먼저 s를 n으로 나눈 몫을 구한다. 일단은 집합을 이 몫으로 n개만큼 채운다. 나머지는 n보다 작을 것이기 때문에 나머지를 각각 1씩 나눠서 집합의 마지막 순서부터 차례로 더해주면 최고의 집합을 구할 수 있다.

(ex: n = 5, s = 17이면 먼저 집합을 17 / 5의 몫인 3으로 가득 채운다({ 3, 3, 3, 3, 3 }). 그리고 나서 나머지인 2를 1씩 나눠서 뒤에서부터 더해준다({ 3, 3, 3, 4, 4 }).)

 

처음에 풀 때 아무 생각 없이 DFS를 하였으나 바로 시간 초과가 났다. n이 10,000 이하의 자연수이고, s가 100,000,000이하의 자연수로 매우 크기 때문이다.