[프로그래머스][LV2][C++]숫자 블록

 

이 문제에서 중요한 점은

⭐ 블록에 적힌 번호가 n일때 가장 첫 블록은 n*2번째 위치에 설치하고 그 다음은 n*3, n*4에 설치한다.

⭐ 기존에 설치된 블록을 빼고 새로운 블록을 집어 넣을 수 있다

⭐ 만약 1부터 시작이라면 입출력 예시와 같이 제일 앞에 0이 있어야한다. 

이때 12번 블록에 들어갈 블록을 생각해보면 

12번 블록의 약수는 1,2,3,4,6,12이다 이때 최종적으로 들어가게 되는 블록은 제일 큰 약수인 6이다. 

만약 6번째 블록은 12번째 블록에 설치되는 것이다. 

이 약수는 제일 작은 약수에서 원래 값을 나누어주면 된다.

그리고 이 약수가 10,000,000보다 낮은 경우에만 블록으로 사용 가능하기 때문에 만약 가장 큰 약수가 이 보다 크다면 앞에서부터 숫자를 늘려가면서 원래값에 나눠주면 그보다 작은 값을 얻을 수 있다.

#include <string>
#include <vector>
#include <cmath>
using namespace std;
const int MAX_VALUE=10000000;

long long FindMaxDiv(int num)
{
    long long result=1;
    
    for(int i=2;i<=sqrt(num);i++){
        if(num%i==0){
            result=i;
            
            if(num/i<=MAX_VALUE){
                result=num/i;
                break;
            }
        }
    }
    
    return result;
}

vector<int> solution(long long begin, long long end) {
    vector<int> answer;
    for(int i=begin;i<=end;i++){
        if(i==1){
           answer.push_back(0);
           continue;
        }
        answer.push_back(FindMaxDiv(i));
    }
    return answer;
}