C++ 재귀로 풀기: N 이하의 수 중 자릿수 곱이 최대가 되는 값 찾기

양의 정수 N이 하나 주어졌다고 가정해 봅시다. 이때 우리의 목표는 N보다 작거나 같은 모든 수 중에서 각 자릿수의 곱이 가장 커지는 값을 찾는 것입니다.

예를 들어 N이 390이라면 결과는 216입니다. 왜냐하면 389라는 수의 자릿수 곱이 3 × 8 × 9 = 216으로, 390 이하의 어떤 수보다도 크기 때문입니다.

문제 해결 접근 방식

이 문제는 재귀(recursion)를 이용해 우아하게 해결할 수 있습니다. 핵심 아이디어는 다음 두 가지 선택지 중 더 큰 곱을 고르는 것입니다.

• 현재 수의 마지막 자릿수를 그대로 사용하는 경우
• 앞자리 부분(N / 10)을 1 감소시켜 마지막 자릿수를 9로 만드는 경우 — 자릿수를 내리면 올림수 없이 9를 얻을 수 있어 곱이 커질 가능성이 있습니다.

재귀 함수의 종료 조건은 다음과 같습니다.

• N이 0이면 1을 반환합니다.
• N이 10 미만이면 N을 그대로 반환합니다.

그 외의 경우에는 다음 식을 반환합니다.
max( max_product(N / 10) × (N % 10), max_product(N / 10 − 1) × 9 )

C++ 구현 예제

#include<iostream>
using namespace std;

int max_product(int N) {
    if (N == 0)
        return 1;
    if (N < 10)
        return N;
    return max(max_product(N / 10) * (N % 10),
               max_product(N / 10 - 1) * 9);
}

int main() {
    int N = 432;
    cout << "Maximum product is: " << max_product(N);
}

실행 결과

Maximum product is: 243

N이 432일 때 출력값은 243입니다. 실제로 432 이하의 수 중에서는 399의 자릿수 곱인 3 × 9 × 9 = 243이 최댓값이므로, 알고리즘이 올바르게 동작함을 확인할 수 있습니다.

동작 원리 요약

이 알고리즘은 각 단계에서 마지막 자릿수를 유지할지, 아니면 앞자리를 하나 줄여 9로 바꿀지를 비교하며 최적의 곱을 탐색합니다. 이러한 방식 덕분에 0부터 N까지 모든 수를 일일이 확인하는 브루트포스 방식(O(N))보다 훨씬 효율적으로, 자릿수에 비례하는 시간 안에 답을 구할 수 있습니다.