[수학] 프로그래머스 '최고의 집합' - js

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

프로그래머스

2. 코드

이 문제는 수학적 개념을 사용하면 쉽지만 모든 경우의 수를 다 구하려면 'n은 1 이상 10,000 이하의 자연수' 라는 조건에 막혀 허덕일 것이다. 테케를 보면 정답은 항상 요소간의 편차가 적은 경우가 된다.

예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

자연수 2개로 이루어진 집합 중 원소의 합이 8인 집합은 다음과 같습니다.
{ 1, 7 }, { 2, 6 }, { 3, 5 }, { 4, 4 }
그중 각 원소의 곱이 최대인 { 4, 4 }가 최고의 집합입니다.

이를 이용해서 문제를 풀면 된다. 

편차가 가장 적은 경우를 고려하였을 때, 정답 배열의 첫 요소는 s / n 로 두면 된다. s / n 부터 시작해서 편차를 최대한 줄여나가야 그 요소들의 곱이 최대값이 될 수 있기 때문이다.

이때 s와 n이 나누어 떨어지지 않는 경우가 생길 것 이다(n = 2, s = 9 일 때). 나누어 떨어지지 않는다는 것은 그 남은 만큼을 집합 중 첫 요소를 제외한 나머지 요소에 다시 배분할 수 있다는 것을 뜻한다. 집합은 오름차순으로 되어 있기 때문에, 뒤에서부터 나머지의 값이 0이 될 때 까지 1씩 더해주면 될 것 이다. 

function solution(n, s) {
    // 예외
    if(n > s) return [-1];
    // 집합의 첫 요소를 s/n부터 시작하여 집합 요소 간의 편차 줄이기
    const answer = new Array(n).fill(Math.floor(s / n));
  	// s/n 나머지를 남은 요소들에게 나눠주기
    for(let i = 0; i < s % n; i ++)
        answer[answer.length - 1 - i]++;
  
    return answer;
}

 

나머지 부분을 어떻게 해야 고민하다가 정답을 보고 이해한 문제다. 이해하고 나니 쉬운데ㅠㅠ

 

복기

5/30