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

N = 8인 경우, 8을 그대로 사용하는 것(8)보다 나누어 계산한 값의 합(9)이 더 크므로 최댓값은 9가 됩니다.

접근 방법

핵심 아이디어는 간단합니다. 나눈 값에 대해 동일한 함수를 반복적으로 호출하는 것입니다. 이를 효율적으로 처리하기 위해 동적 프로그래밍(Dynamic Programming) 개념을 활용합니다. 0부터 N까지의 F(i) 값을 배열에 미리 계산하여 저장하고, 이후 계산에서 재사용함으로써 불필요한 중복 연산을 제거하고 해답을 빠르게 찾을 수 있습니다.

즉, 각 i에 대해 F(i/2) + F(i/3) + F(i/4) + F(i/5)의 합이 i보다 크면 그 합을, 그렇지 않으면 i 자체를 F(i)로 저장하는 방식으로 진행됩니다.

구현 예제

#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<<"나누기 또는 그대로 사용 중 최댓값 = "<<calcMaximumValue(N);
   return 0;
}

실행 결과

나누기 또는 그대로 사용 중 최댓값 = 9

복잡도 분석

이 알고리즘은 0부터 N까지 한 번씩만 계산하므로 시간 복잡도는 O(N), 결과를 저장하는 배열을 사용하므로 공간 복잡도 역시 O(N)입니다. 재귀 호출 대신 반복문과 메모이제이션을 함께 사용하기 때문에 큰 N 값에서도 안정적인 성능을 보여줍니다.