C++에서 숫자가 2개의 삼각형 숫자의 합으로 표시될 수 있는지 확인

이 섹션에서는 하나의 수를 두 개의 삼각형 수의 합으로 표현할 수 있는지 여부를 알아보겠습니다. 삼각수는 아래와 같습니다 -

이 예에서 1, 3, 6, 10이 일부 삼각형 숫자임을 알 수 있습니다. 숫자 N(예:16)을 두 개의 삼각형 숫자(6, 10)의 합으로 표현해야 합니다.

접근 방식은 매우 간단합니다. N보다 작은 모든 삼각수를 가져와야 합니다. 이 값으로 집합을 만드세요. 이제 집합에서 X라는 숫자를 가져와서 N – X가 집합에 존재하는지 확인해야 합니다. 그러면 X는 두 개의 삼각형 숫자의 합으로 표시될 수 있습니다.

예시

#include <iostream>
#include <set>
using namespace std;
bool isSumTriangularNum(int n) {
   set<int> s;
   int i = 1;
   while (1) { //find and store all triangular numbers below n, and store into set
      int x = i * (i + 1) / 2;
      if (x >= n)
         break;
      s.insert(x);
      i++;
   }
   for (auto x : s)
   if (s.find(n - x) != s.end())
   return true;
   return false;
}
int main() {
   int num = 16;
   if(isSumTriangularNum(num)){
      cout << "Can be represented";
   }else{
      cout << "Cannot be represented";
   }
}

출력

Can be represented