C++로 숫자의 거듭제곱 가중치를 활용해 저울 균형 맞추기

문제 개요

주어진 가중치, 즉 어떤 수의 거듭제곱 형태의 추들을 사용하여 저울의 양쪽 접시 균형을 맞추는 것이 이번 문제의 목표입니다.

문제 설명

이 문제에서는 저울 방식의 측정 장치가 주어집니다. 목표 무게 T와 함께, 어떤 수 a의 거듭제곱 값을 가진 여러 개의 추가 제공됩니다. 우리는 이 추들을 활용해 저울의 양팔을 균형 있게 만들어야 합니다.

이때 성립해야 하는 방정식은 다음과 같습니다.

T + (a의 어떤 거듭제곱) = (a의 다른 거듭제곱)

주의할 점은 각 거듭제곱 값에 해당하는 추가 정확히 하나씩만 존재한다는 것입니다.

예시

T = 12 : a = 4

아래와 같이 추를 배치하면 균형을 이룰 수 있습니다.

12 + 4 = 16

접근 방법

이 문제를 해결하려면 T를 a의 거듭제곱들의 합으로 표현해야 합니다. 이를 위해 T를 10진법에서 a진법으로 변환하고, 변환된 결과를 분석합니다.

케이스 1 — 0과 1로만 구성된 경우

진법 변환 후 표현된 값이 0과 1로만 이루어져 있다면, 1이 있는 자리에 해당하는 추들을 더하기만 하면 T의 값을 만들 수 있습니다.

예를 들어 보겠습니다.

T = 10 : a = 3

10을 3진법으로 변환하면 101이 됩니다. 따라서 3⁰과 3², 즉 (1 + 9) = 10으로 저울을 균형 있게 만들 수 있습니다.

케이스 2 — 그 외의 숫자가 포함된 경우

진법 변환 후 0과 1 이외의 값이 나타난다면, 추가적인 처리 과정이 필요합니다. 이 경우 해답이 존재하기 위한 필수 조건은 해당 자릿값이 (a - 1)이어야 한다는 것입니다. 조건을 만족하면 그 거듭제곱에 해당하는 추를 T 쪽으로 옮기고, 진법 표현의 해당 자릿수를 1 증가시킵니다(자리올림).

예를 들어 보겠습니다.

T = 7 : a = 3

7을 3진법으로 변환하면 021이 됩니다. 여기서 3¹에 해당하는 추를 T 쪽으로 옮기고 반대편 숫자를 1 증가시키면 값이 10이 되고, 이는 다시 101, 즉 (9 + 1)로 표현됩니다. 따라서 균형을 이룰 수 있습니다.

위 두 가지 케이스를 바탕으로 문제를 해결하는 프로그램을 작성할 수 있습니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
bool isBalancePossible(int T, int a){
   vector<int> baseForm;
   while (T) {
      baseForm.push_back(T % a);
      T /= a;
   }
   baseForm.push_back(0);
   for (int i = 0; i < baseForm.size(); i++) {
      if (baseForm[i] != 0 && baseForm[i] != 1 &&
      baseForm[i] != (a - 1) && baseForm[i] != a)
      return false;
   if (baseForm[i] == a || baseForm[i] == (a - 1))
      baseForm[i + 1] += 1;
   }
   return true;
}
int main(){
   int T = 21;
   int a = 4;
   if (isBalancePossible(T, a))
      cout << "Balance is possible" << endl;
   else
      cout << "Balance is not possible" << endl;
   return 0;
}

실행 결과

Balance is possible