[Programmers] 숫자 블록

숫자 블록

그렙시에는 숫자 0이 적힌 블록들이 설치된 도로에 다른 숫자가 적힌 블록들을 설치하기로 하였습니다. 숫자 블록을 설치하는 규칙은 다음과 같습니다.
블록에 적힌 번호가 n 일 때, 가장 첫 블록은 n 2번째 위치에 설치합니다. 그 다음은 n 3, 그 다음은 n * 4, ...위치에 설치합니다. 기존에 설치된 블록은 빼고 새로운 블록을 집어넣습니다.
...
그렙시는 길이가 1,000,000,000인 도로에 1부터 10,000,000까지의 숫자가 적힌 블록들을 이용해 위의 규칙대로 모두 설치 했습니다.
...
구간을 나타내는 두 정수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열을 return하는 solution 함수를 완성해 주세요.

풀이

시간 안에 구현하지 못해서 다른 사람들의 풀이를 참고했다.
핵심은 현재 숫자 n의 1과 자기자신을 제외한 가장 큰 약수를 찾아야 한다.

1. n mod i == 0인 찾는다. i는 [2, sqrt(n)] 값을 가진다.
2. 또한, n/i <= 10^7 을 만족하면 i은 n의 가장 작은 약수가 되고, (n-1)은 n의 가장 큰 약수가 된다.
3. 블록의 값은 (n-1)이다.

• 예외사항
  • n==1 이면 블록의 값은 항상 0이다.
  • 블록의 최대 길이는 10^9이다. 따라서, (n/i)이 10^7보다 크면 조건에 위배된다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(long long begin, long long end) {
    vector<int> answer;
    
    for(long long n=begin; n<=end; n++){
        if(n==1){
            answer.push_back(0);
            continue;
        }
        
        long long div=1; 
        for(long long i=2; i<=sqrt(n); i++){
            if(n%i==0){
                div = i; // n의 가장 큰 약수
                if((n/i) <= 10000000){
                    div = n/i; // n의 가장 작은 약수
                    break;
                }
            }
        }
        answer.push_back(div);
    }
    
    return answer;
}

정리

참고
위배사항 참고