[JS] 최고의 집합

그리디를 활용해서 해결하였다.

 

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

프로그래머스

 

언뜻 보면 조합으로 탐색을 해야할 것 같지만 그리디로 해결할 수 있다.

 

 

S란 수를 N개로 나누면 우선 S를 N으로 나누어 준다.

 

9를 5개로 나눠보자.

 

9/5 -> 1.xxxx

 

{1,1,1,1,1} 여기서 9%5 는 4이다.

 

따라서 뒤에서부터 4개의 값에 1씩 더해주면 된다.

 

{1,2,2,2,2}

 

 

 

이 방법이 가능한 이유는 합을 만들 수 있는 조합중에서 곱이 크려면 모든 수가 최대한 중앙에 붙어있어야 하기때문

 

 

function solution(n, s) {
    if(s/n < 1) return [-1]
    const num = ~~(s/n)

    const ret = Array(n).fill(num)
    for (let i = 1 ; i <= s%n ; i++){
        ret[n-i] += 1
    }
    return ret
}

 

 

약간 멋(?) 을 부리면 아래처럼도 할 수 있다.

 

const solution = (엄, 준) => 준/엄 >= 1 ? Array(엄).fill(~~(준/엄)).map((식,i) => i>=엄-준%엄 ? 식+1:식 ) :[-1]