[leetCode/JS] 343. Integer Break

난이도 [ 🤔 ] Medium

문제 설명

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

 

Return the maximum product you can get.

 

입출력 예

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

 

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Constraints

• 2 <= n <= 58

---

내 솔루션

• 1 부터 12까지 손으로 계산해보고 규칙이 있는지 확인해봤다.

// 여긴 예외
// 2: 1 1 = 1
// 3: 2 1 = 2

// 그냥 3이 많으면된다.
// 4: 2 2 = 4
// 5: 3 2
// 6: 3 3
// 7: 3 2 2
// 8: 3 3 2
// 9: 3 3 3
// 10: 3 3 2 2
// 11: 3 3 3 2
// 12: 3 3 3 3

• 결론은 3이 많으면 된다.
• 2, 3은 예외처리로 n - 1 한다.
• 4 ~ n 은 4보다 크면 3으로 빼고, 4이하는 그대로 사용한다. ( result * 4 === result * 2 * 2 이므로 )
• 그래서 아래와 같이 코드가 나왔다.

 

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
  if(n === 2 || n === 3) return n - 1;
  let result = 1;
  while(n > 4){
    result *= 3
    n -= 3
  }
  return result * n
};

 

감상평

• 이런게 진짜 재미있는 문제 아닐까?
• leetCode 특유의 이해하기 쉬운 간결한 문제와 짧고 맛있는 풀이 과정
• 이걸 DP나 DFS로 푼 사람들도 있던데.. 진짜 들은 다른 세상에 사는 거 같다.