최고의 집합

문제 링크

문제 요약

• 최고의 집합을 찾아주세요

  • 각 원소의 합이 S가 되는 수의 집합
  • 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합
• 집합의 요소는 자연수로 이루어집니다.

제한사항

• 최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
• 만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
• 자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
• 모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

Input

• 집합의 원소의 개수 n
• 모든 원소들의 합 s

output

• 최고의 집합을 return

해결방법

• 처음에는 경우의 수를 모조리 선언해놓고 시작할 작정이었는데…

• 잘 생각해보니 최고의 집합이 되려면 가져야 하는 조건이 생각보다 단순하다.

  • 각 원소의 곱이 최대가 되려면 각 원소의 값이 크게 차이가 나는 것보다 사이좋게 비슷한 숫자를 이루는 편이 유리하다.
  • 예제 숫자를 두고 몇 번 확인을 해보니 각 원소가 중위값을 가질 수록 곱이 크다는 것은 참인 것으로 판단됨
• 각 원소가 고르게 높으면서 부족한 합은 1씩 채워주면 최고의 집합이 나온다

function solution(n, s) {
  const baseNum = Math.floor(s / n)
  const addCount = s % n
  if (baseNum === 0) return [-1]
  return [
    ...new Array(n - addCount).fill(baseNum),
    ...new Array(addCount).fill(baseNum + 1),
  ]
}

• baseNum을 구한다.

  • 총 합을 각 원소끼리 사이좋게 나눠갖는다.

• addCount를 구한다.

  • 나눠가지고나서 총 합에서 부족한 값이 얼마인지 구한다.
• 만약 baseNum이 0이라면 [-1]을 반환한다.(0은 자연수가 아니므로)
• n-addCount 만큼의 baseNum와 addCount 만큼의 baseNum+1로 이루어진 배열을 반환한다.