문제 링크

프로그래머스 문제

풀이

처음에는 모든 경우의 수를 모두 만들어 보면서 완전탐색으로 해결하려 했습니다.
하지만 해당 방식은 시간복잡도가 너무 높아 실패 했습니다.
따라서 다음과 같은 생각을 따라가기로 했습니다.

1. 가장 곱이 높은 경우는 얼마인가?
2. 일반적으로 두 수의 합이 고정되어 있는 경우, 두 수가 같거나 차이가 적을때, 그 곱이 가장 큰 값이 나온다는 점에서 문제의 실마리를 찾음
3. 예를들어 1,3 의 곱보다 2 ,2 의 곱이 큰값을 가짐

따라서 문제를 해결하기 위해 애초에 제공받은 숫자를 나누고 추가하는 방식을 사용하였습니다.

floor 함수는 내림 함수 입니다. 비슷한 함수로 ceil, round가 있습니다.

코드

function solution(n, s) {
    let array = new Array(n).fill(Math.floor(s/n))

    const dif = s - (Number(n)*Number(array[0]))
 
    for(let i=0; i< dif; i++){
        array[i] += 1;
    }
    
    return s>n ? array.sort((a,b) => a-b) : [-1]
}

// 입력받은 n에 대해서 합이 s로 만드는 집합들을 만들어야 한다. 

// 아니다 이거 집합 만들기 너무 힘들어
// 그러면 s를 n으로 나누고 그럴듯한 숫자를 만들면 어떨까?

// 처음 시도는 s 로 나누면 다 1로 나눈것과 같으니 그걸 이용하려 했다
// 근데 어차피  1에 가까워질 수록 나눈 그 값을 몇개의 숫자로 뿌리는 과정이 그냥 우리가 원하는 과정이다
// 따라서 그냥 우리가 원하는 과정을 먼저 만들려고 해야함
// 아 알아버렸다


// 1 8 => 8
// 2 8 => 4 4
// 3 8 => 2 3 3 => 18,2 2 4 
// 4 8 => 2 2 2 2
// 5 8 => 1 1 2 2 2
// 6 8 => 1 1 1 1 2 2
// 7 8 => 1 1 1 1 1 1 2


// 1 9 => 9
// 2 9 => 4 5
// 3 9 => 3 3 3
// 4 9 => 2 2 2 3
// 5 9 => 1 2 2 2 2
// 6 9 => 1 1 1 2 2 2
// 7 9 => 1 1 1 1 1 2 2
// 8 9 => 1 1 1 1 1 1 1 2

// 1 10 => 10
// 2 10 => 5 5
// 3 10 => 3 3 4
// 4 10 => 2 2 3 3
// 5 10 => 1 2 2 2 2
// 6 10 => 1 1 1 2 2 2
// 7 10 => 1 1 1 1 1 2 2
// 8 10 => 1 1 1 1 1 1 1 2