문제 출처

1. 문제설명

  • 최대 10,000,000까지의 숫자가 적힌 블록이 있다.
  • 문제가 길어 요약하자면, 각 위치의 블록에 자신을 제외한 가장 큰 약수를 채워넣으면 된다.
  • 이후 begin ~ end 구간에 해당하는 숫자를 출력한다.


2. 입/출력

  • 입력
    • 구간을 나타내는 두 정수 begin, end
  • 출력
    • 구간에 깔려 있는 블록의 숫자 배열을 return


3. 문제 분류

  • Math


4. 알고리즘 설계

  • 문제에 설명된 것처럼 1부터 마지막 숫자까지 for문으로 계속 갱신하면 무조건 시간 초과다.
    • N이 너무 크기 때문이다.
  • n의 값에 대한 약수 중 자신을 제외한 가장 큰 약수를 계산해야 한다.
    • 약수 중 가장 작은 값은 반드시 1이다.
    • 1 이상의 어떤 수는 1 x n이 자기 자신이 되기 때문이다.
    • 즉, 약수가 없다면 1을 반환하면 된다는 의미이다.
  • 약수 계산하기
    • 10의 약수는 {1, 2, 5, 10}이 된다.
    • 이걸 전부 일일히 구할 수도 있지만 좋은 방법이 하나 있다.
    • 10을 어떤 약수로 나누면 그 매칭되는 값을 구할 수 있다는 것.
    • 예를 들어
      • 10을 2로 나눈 나머지가 0이기 때문에 약수에 해당한다.
      • 또한, 10을 2로 나눈 몫 또한 10의 약수가 된다.
      • 왜? 2 x (10 / 2) = 10을 성립하기 때문이다.
    • 다시 말해서, 10의 제곱근 값까지만 탐색하면서 10으로 나눴을 때 값이 가장 큰 걸 리턴하면 된다.
  • 문제 잘 읽기
    • 1부터 10,000,000까지의 숫자가 적힌 블록들을 이용해 라는 문구가 있다.
    • 즉, 10,000,000이하의 가장 큰 약수를 취해야 한다.
    • 10,000,000보다 크다면 1을 리턴하는 게 아니다!


5. 전체 코드

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

LL _find(LL n) {
    LL ret = 1;
    
    for(LL i = 2; i <= sqrt(n); i++) {
        if(n % i == 0) {
            ret = i;
            
            if(n / i <= 10'000'000) {
                ret = n / i;
                break;
            }
        }
    }
    
    return ret;
}

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