C++ 프로그램 그대로 나누거나 고려한 최대값

이 문제에서 우리는 숫자 N을 받습니다. 우리의 임무는 C++에서 나누거나 고려하는 것을 선택하여 최대값을 찾는 프로그램을 만드는 것입니다.

문제 설명

최대값을 찾기 위해 값을 그대로 사용하거나 나누어 최대값을 얻을 수 있는 두 값을 고려할 수 있습니다. 값은 F(N/2) + F(N/ 3) + F(N/4) +F(N/5) .

문제를 이해하기 위해 예를 들어보겠습니다.

입력 :N =8

출력 :9

설명

F(8) =F(8/2) + F(8/3) + F(8/4) + F(8/5) =F(4) + F(2) + F(2) + F( 1) =4 + 2 + 2 + 1 =9

해결 방법

아이디어는 단순히 나눗셈 값에 대해 동일한 함수를 여러 번 호출하는 것입니다. 이를 위해 동적 프로그래밍이라는 개념을 사용하고 F(i) 값을 0에서 N까지 풀기 위한 배열을 만들어 솔루션을 찾는 데 재사용하도록 했습니다.

예

#include <iostream>
using namespace std;
int calcMaximumValue(int N) {
   int F[N + 1];
   int divVal = 0;
   F[0] = 0;
   F[1] = 1;
   for (int i = 2; i <= N; i++) {
      divVal = ( F[i / 2] + F[i / 3] + F[i / 4] + F[i / 5] );
      if(divVal > i)
         F[i] = divVal;
      else
         F[i] = i;
   }
   return F[N];
}
int main() {
   int N = 8;
   cout<<"Maximum value with the choice of either dividing or considering as it is = "<<calcMaximumValue(N);
   return 0;
}

출력

Maximum value with the choice of either dividing or considering as it is = 9