[프로그래머스 2레벨] 숫자 블록 (C++)

#include <string>
#include <vector>

using namespace std;

long long cal(long long n)
{
    long long result=1;
    for(long long i=2; i*i<=n; i++)
    {
        if(n%i==0)
        {
            result = i;
            if(n/i <= 10000000)
            {
                result = n/i;
                break;
            }
        }
    }
    return result;
}

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

 

i의 약수 중, 자기 자신을 제외한 가장 큰 약수를 구하는 문제이다.

예외처리로 첫 시작점은 0으로 해주고, 기본 값은 1이다.

이후에 현재 n(begin~end) 값이 나눠진다면 우선 해당 값을 후보 값으로 지정하고, n/i<=10000000을 통해 나눠진다면 이를 통해 가장 큰 약수를 구하고 반복문을 종료한다.

 

배수마다 값이 덮어씌워진 걸 생각하여, 현재 위치의 값은 현재 값의 약수만 올 수 있다는 것을 감안한 문제이다.

단 배수가 2부터 시작되기에, 현재 위치에 자기 자신은 올 수 없다.

이때문에 자기 자신은 가장 큰 약수에서 제외한다.