아래가 2,3,5만을 약수로 가지는 n번째 해밍수를 구하는 코드입니다.

 for문에서 시간이 오래 걸리는 것 같은데 어떻게 해야 더 빠르게 구할 수 있을지 감이 잘 안잡힙니다.

조언해 주시면 감사하겠습니다 ㅠ

 

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

int objectNum;
int *hammingNum;
int hammingDivi[3] = { 2,3,5 };
int mini= 2147483647, index=1;

bool isExist(int num, int j)
{
 for (int i = 0; i < j; i++)
  if (hammingNum[i] == num)
  {
   return true;
  }
 return false;
}

void Calmin(int multi)
{
 if (mini > multi)
  mini = multi;
}

int main()
{
 int testcaseNum;

 ifstream file;
 file.open("input.txt");

 file >> testcaseNum;

 for (int i = 0; i < testcaseNum; i++)
 {
  file >> objectNum;
  hammingNum = new int[objectNum];
  hammingNum[0] = 1;

  for (int i = 1; i < objectNum; i++)
  {
   for (int x = 0; x < i; x++)
   {
    for (int y = 0; y < 3; y++)
    {
     int multi = hammingNum[x] * hammingDivi[y];
     if (isExist(multi, i)==false)
      Calmin(multi);
    }
   }
   hammingNum[i] = mini;
   mini = 2147483647;
  }
  cout << hammingNum[objectNum-1] << endl;
 }

 return 0;
}