문제 설명
그렙시에는 숫자 0이 적힌 블록들이 설치된 도로에 다른 숫자가 적힌 블록들을 설치하기로 하였습니다. 숫자 블록을 설치하는 규칙은 다음과 같습니다.
블록에 적힌 번호가 n 일 때, 가장 첫 블록은 n * 2번째 위치에 설치합니다. 그 다음은 n * 3, 그 다음은 n * 4, ...위치에 설치합니다. 기존에 설치된 블록은 빼고 새로운 블록을 집어넣습니다.
블록은 1이 적힌 블록부터 숫자를 1씩 증가시키며 순서대로 설치합니다. 예를 들어 1이 적힌 블록은 2, 3, 4, 5, ... 인 위치에 우선 설치합니다. 그 다음 2가 적힌 블록은 4, 6, 8, 10, ... 인 위치에 설치하고, 3이 적힌 블록은 6, 9, 12... 인 위치에 설치합니다.
이렇게 3이 적힌 블록까지 설치하고 나면 첫 10개의 블록에 적힌 번호는 [0, 1, 1, 2, 1, 3, 1, 2, 3, 2]가 됩니다.
그렙시는 길이가 1,000,000,000인 도로에 1부터 10,000,000까지의 숫자가 적힌 블록들을 이용해 위의 규칙대로 모두 설치 했습니다.
그렙시의 시장님은 특정 구간에 어떤 블록이 깔려 있는지 알고 싶습니다.
구간을 나타내는 두 정수 begin, end 가 매개변수로 주어 질 때, 그 구간에 깔려 있는 블록의 숫자 배열을 return하는 solution 함수를 완성해 주세요.
https://school.programmers.co.kr/learn/courses/30/lessons/12923
제한 사항
- 1 ≤ begin ≤ end ≤ 1,000,000,000
- end - begin ≤ 5,000
풀이
간단한 문제이지만 시간 초과와 제한 사항때문에 어려운 부분이 있다.
우선 기본적인 접근법은 begin부터 end까지 하나씩 살펴보며 2부터 10,000,000까지 나누어 떨어지는 수중 가장 큰 수를 찾으면 된다.
하지만, 수의 범위가 굉장히 크기 때문에 시간 초과가 발생할 수 있다.
이를 해결하기 위해 소수 판별과 비슷하게 제곱근까지의 수만 계산하면 된다.
이 방법이 유효한 이유는 타일은 나누어 떨어지는 수에 깔리기 때문에 제곱근까지만 계산해도 결과가 같다.
이때, 주의해야 하는 부분이 있는데 블록이 10,000,000까지만 사용할 수 있기 때문에 나눈 결과값이 10,000,000보다 큰 경우는 무시해야 한다.
즉, 2부터 시작하여 나누어 떨어지는 결괏값이 가장 큰 수를 빠르게 찾을 수 있지만 결과가 10,000,000보다 큰 경우는 답이 될 수 없다는 뜻이다.
그렇다면 이때 답이 될 수 있는 후보는 나눈 결과값이 아닌 나누는 수가 된다.
10,000,000보다 작은 수중 답을 찾지 못했다면 나누어 떨어지는 수 중 가장 큰 나누는 수가 정답이 된다.
전체 코드
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
vector<int> solution(long long begin, long long end) {
vector<int> answer;
const int MAX = 10'000'000;
for(int i = begin; i <= end; i++)
{
if(i == 1)
{
answer.push_back(0);
continue;
}
bool flag = true;
int temp = 1;
for(int j = 2; j <= sqrt(i); j++)
{
// j는 나누는 수
if(i%j == 0)
{
if(i/j <= MAX)
{
answer.push_back(i/j);
flag = false;
break;
}
temp = max(temp, j);
}
}
if(flag)
{
answer.push_back(temp);
}
}
return answer;
}
