JavaScript로 정수를 나누어 최대 곱 구하기

문제

정수 num을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 주어진 정수를 최소 두 개 이상의 조각으로 나누어야 하며, 각 조각의 합은 num과 같고 곱은 가능한 한 최대가 되어야 합니다. 마지막으로 함수는 이렇게 구한 최대 곱을 반환해야 합니다.

예를 들어, 함수의 입력이 다음과 같다면 −

const num = 10;

출력은 다음과 같아야 합니다 −

const output = 36;

출력 설명

10은 3 + 3 + 4로 나눌 수 있고, 이 세 수를 곱하면 3 × 3 × 4 = 36이 되기 때문입니다. 실제로 10을 어떤 방식으로 나누더라도 36보다 큰 곱은 만들 수 없습니다.

접근 방법: 동적 계획법(DP)

이 문제는 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• dp[i]: 정수 i를 여러 조각으로 나누었을 때 얻을 수 있는 최대 곱을 저장합니다.
• 각 정수 i에 대해 j와 i-j 두 부분으로 나누는 모든 경우를 시도합니다.
• 나눈 각 부분은 그대로 사용하는 것(j)과 더 잘게 쪼개는 것(dp[j]) 중 더 큰 값을 선택합니다.

이렇게 하면 작은 문제의 답을 활용해 큰 문제의 답을 점진적으로 구할 수 있습니다.

예시 코드

이를 구현한 코드는 다음과 같습니다 −

const num = 10;
const breakInt = (num = 2) => {
   const dp = new Array(num + 1).fill(0);
   dp[0] = 0;
   dp[1] = 1;
   for(let i = 2; i <= num; i++){
      for(let j = 1; 2*j <= i; j++){
         dp[i] = Math.max(dp[i], Math.max(j, dp[j]) * Math.max(i-j,
         dp[i-j]) );
      };
   };
   return dp[num];
};
console.log(breakInt(num));

코드 설명

• 먼저 num+1 크기의 배열 dp를 만들고 0으로 초기화합니다.
• 내부 반복문에서 j는 1부터 i/2까지만 순회합니다. j와 i-j는 대칭적이므로 절반만 확인하면 충분합니다.
• Math.max(j, dp[j]): j를 그대로 곱에 사용할지, j를 더 쪼개서 얻는 값(dp[j])을 사용할지 결정합니다.

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다 −

36

이 알고리즘의 시간 복잡도는 O(n²), 공간 복잡도는 O(n)으로, 비교적 큰 입력값에도 효율적으로 동작합니다.