C++의 정수 나누기

양의 정수 n이 있다고 가정하면 이를 최소 두 개의 양수의 합으로 나누고 그 정수의 곱을 최대화해야 합니다. 우리는 우리가 얻을 수 있는 최대의 제품을 찾아야 합니다. 따라서 숫자가 10이면 답은 36이 됩니다. 10 =3 + 3 + 4, 3 * 3 * 4 =36

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

solve() 메서드를 정의하면 n, 배열 dp 및 플래그가 필요합니다.
n이 0이면 1을 반환합니다.
dp[n]이 -1이 아니면 dp[n]
를 반환합니다.
end :=n – 플래그가 설정되면 1, 그렇지 않으면 n
ret :=0
범위 1에서 끝까지의 i에 대해
- ret :=ret 및 i*의 최대값 solve(n – i, dp, false)
set dp[n] :=ret 및 반환
기본 방법에서 크기가 n + 1인 배열 dp를 만들고 – 1
로 채웁니다.
해결(n, dp) 반환

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(int n, vector <int>& dp, bool flag = true){
      if(n == 0) return 1;
      if(dp[n] != -1) return dp[n];
      int end = flag? n - 1: n;
      int ret = 0;
      for(int i = 1; i <= end; i++){
         ret = max(ret, i * solve(n - i, dp, false));
      }
      return dp[n] = ret;
   }
   int integerBreak(int n) {
      vector <int>dp(n + 1, -1);
      return solve(n, dp);
   }
};
main(){
   Solution ob;
   cout << (ob.integerBreak(10));
}

C++의 정수 나누기

예시(C++)

입력

출력