C++로 n에 d의 배수를 더한 후 가능한 최소 자릿수 합 구하기

문제 개요

이 문제에서는 두 개의 정수 n과 d가 주어지며, n에 d의 배수를 더했을 때 얻을 수 있는 최소 자릿수 합(digit sum)을 구하는 것이 목표입니다.

문제 설명: n에 d의 k번째 배수를 더하여 자릿수 합을 최소화해야 합니다.

예시를 통해 문제를 살펴보겠습니다.

입력

n = 5230, d = 54

출력

1

설명

n + (2 × d) = 5230 + (2 × 54) = 5338

해결 접근 방법

가장 간단한 풀이 방법은 d의 배수를 1배부터 8배까지만 확인하는 것입니다. 9번째 배수부터는 자릿수 합이 다시 반복되기 때문입니다. 이 원리는 모듈로 9(modulo 9) 연산에 기반합니다. 어떤 수를 9로 나눈 나머지는 그 수의 디지털 루트, 즉 자릿수를 한 자리가 될 때까지 반복해서 더한 값과 같기 때문입니다. 수식으로 표현하면 (n + d·(9k + l)) mod 9 는 (n + d·l) mod 9 와 항상 동일합니다.

따라서 l = 1부터 8까지 각각의 경우에 대해 n + l·d 의 자릿수 합을 계산하고, 그중 가장 작은 값을 반환하면 됩니다.

여기에 한 가지 최적화를 추가할 수 있습니다. 자릿수 합은 절대 1보다 작아질 수 없으므로, 탐색 도중 자릿수 합이 1이 되면 더 이상 진행하지 않고 즉시 그 값을 반환하는 것입니다.

구현 예제

#include <iostream>
using namespace std;
int calcDigitSum(int n) {
    int i = n % 9;
    if (i == 0)
        return 9;
    else
        return i;
}
int findMinDigitSum(int n, int d) {
    int minSum = 10;
    int number;
    for (int i = 1; i < 9; i++) {
        number = (n + i * d);
        minSum = min(minSum, calcDigitSum(number));
        if(minSum == 1)
            return minSum;
    }
    return minSum;
}
int main() {
    int n = 5230, d = 54;
    cout<<"The minimum possible digitsum after adding the number is "<<findMinDigitSum(n, d);
    return 0;
}

출력

The minimum possible digitsum after adding the number is 1