C++로 2부터 N/2까지 모든 진법에서 숫자 N의 자릿수 합 구하기

이 문제에서는 하나의 숫자 N이 주어지며, 2부터 N/2까지의 모든 진법으로 숫자 N을 표현했을 때 각 자릿수의 합을 구하는 프로그램을 작성하는 것이 목표입니다.

즉, 숫자 N의 진법을 2부터 N/2까지 차례대로 바꿔가며 계산해야 합니다. 예를 들어 n = 9라면 적용되는 진법은 2, 3, 4이고, 각 진법으로 표현한 숫자의 모든 자릿수를 더한 값을 구해야 합니다.

문제 이해를 위한 예시

입력:

N = 5

출력:

2

설명:

2부터 N/2(=2)까지의 진법은 2 하나뿐입니다.
5를 2진법으로 표현하면 101이며, 자릿수의 합은 1 + 0 + 1 = 2입니다.

해결 접근 방식

이 문제를 해결하려면 2부터 N/2까지의 모든 숫자를 진법으로 하나씩 사용합니다. 각 진법에서 자릿수의 합을 계산하는 방법은 다음과 같습니다.

• N을 해당 진법으로 나눈 나머지(N % base)를 합계에 더합니다.
• N을 해당 진법으로 나눈 몫(N = N / base)으로 갱신합니다.
• N이 0이 될 때까지 위 과정을 반복합니다.

이렇게 각 진법별로 구한 자릿수 합을 모두 누적하면 최종 결과를 얻을 수 있습니다.

구현 예제

아래는 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;
int findBaseSum(int n, int base, int &sum){
    while (n > 0) {
        sum += n % base;
        n /= base;
    }
return sum;
}
void CalcSumOfBaseDigits(int n, int &sum){
    for (int base = 2; base <= n / 2; base++)
        findBaseSum(n, base, sum);
}
int main(){
    int N = 11;
    int sum = 0;
    CalcSumOfBaseDigits(N, sum);
    cout<<"The sum of digits of "<<N<<" written in all bases from 2 to "<<(N/2)<<" is "<<sum;
    return 0;
}

실행 결과

The sum of digits of 11 written in all bases from 2 to 5 is 14

숫자 11을 각 진법으로 표현하면 2진법에서는 1011(자릿수 합 3), 3진법에서는 102(자릿수 합 3), 4진법에서는 23(자릿수 합 5), 5진법에서는 21(자릿수 합 3)이 되며, 이를 모두 더한 값 14가 최종 결과로 출력됩니다.