C++로 구현하는 합이 N이 되는 최소 거듭제곱 항의 개수 알고리즘

문제 설명

두 개의 양의 정수 N과 X가 주어집니다. 이때 N을 X의 거듭제곱들의 합(X⁰ + X¹ + … + Xⁿ)으로 표현하되, 사용되는 거듭제곱 항의 개수가 최소가 되도록 만드는 것이 목표입니다.

즉, 합이 N과 같아지도록 하기 위해 사용해야 하는 X의 거듭제곱 항의 최소 개수를 출력하면 됩니다.

예를 들어 N = 15이고 X = 3이라면, '3'의 거듭제곱 3개를 사용하여 다음과 같이 표현할 수 있습니다.

15 = (3² + 3¹ + 3¹)

알고리즘

다음 공식을 활용하면 최종 결과를 손쉽게 계산할 수 있습니다.

1. x = 1인 경우, 답은 n 그 자체입니다 (n = 1 + 1 + … 을 n번 더한 값)
2. 임의의 수 n은 n = x * a + b (단, 0 ≤ b ≤ x-1) 형태로 표현할 수 있습니다. b는 0부터 x-1 사이의 값이므로, b는 x0을 b번 더한 합으로 표현됩니다.

여기서 핵심 아이디어는 n을 x진법으로 변환했을 때 각 자릿수의 합이 곧 필요한 거듭제곱 항의 최소 개수라는 점입니다. 따라서 n을 x로 나눈 나머지를 계속해서 더하고, n을 x로 나누는 과정을 n이 0이 될 때까지 반복하면 정답을 구할 수 있습니다.

예제 코드

#include <iostream>
using namespace std;
int minNumOfPower(int n, int x){
   if (x == 1) {
      return n;
   }
   int result = 0;
   while (n > 0) {
      result = result + (n % x);
      n = n / x;
   }
   return result;
}
int main(){
   int n = 15;
   int x = 3;
   cout << "Minimum number of powers = " <<
   minNumOfPower(15, 3) << endl;
   return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Minimum number of powers = 3

N = 15를 3진법으로 변환하면 120이 되며, 각 자릿수의 합(1 + 2 + 0)은 3입니다. 이는 앞서 살펴본 15 = 3² + 3¹ + 3¹ 표현과 정확히 일치합니다.