[백준 알고리즘] 1016번 제곱 ㄴㄴ수

문제

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다.

 

풀이

해당 문제를 봤을때 처음에는 DP문제인줄 알았다.

하지만 1,2,3 .. i, ... N으로 가면서 규칙성은 없었기 때문에 DP 문제가 아닌 다른 방향의 해석이 필요했다.

처음에 단순히 long long 형태로 처음부터 끝까지 제곱수로 나누는 방식으로는 시간초과로 문제 해결에는 실패했다.

 

다른 방법으로 처음 제곱의 시작점을 잡고 제곱으로 나눴을 때의 몫으로 시작하여 최종적으로 곱해진 값이 Max보다 작았을 때의 경우의 수를 생각하게 되었다. 

 

#include<iostream>

using namespace std;

bool NumArray[1000001]; //최대 백만개까지의 범위이므로

int main() {

	long long min, max;
	cin >> min >> max;

	for (long long i = 2; i * i <= max; i++) {
		long long start = min / (i*i); // 시작점
		if (start * i * i != min) start++;  //ex. min = 29 일 때, 29/4 = 7...1 하지만 7*4 = 28은 min값인 29보다 작으므로 start값을 8로 증가시킨다.
		for (long long j = start; i*i*j <= max; j++) {
			NumArray[i*i*j - min] = true;
		}
	}

	int count = 0;
	for (int i = 0; i < max - min + 1; i++) {
		if (!NumArray[i]) count++;
	}

	cout << count << endl;

}

 

끝.