[백준/C++] 1016번. 제곱 ㄴㄴ 수

문제

1016번: 제곱 ㄴㄴ 수

---

1. 첫 번째 풀이

사고 과정

- 가장 먼저 떠올린 방법은 범위 내의 수를 모든 제곱수를 나눠보는 것이다. min의 최댓값이 1,000,000,000,000(1조)이기 때문에, 가장 큰 제곱수는 1,000,000(백 만)의 제곱인 1조이다. 최악의 경우 1,000,001개의 수를 각각 1,000,000번씩 나눠봐야 한다. 시간복잡도로 따지면 O(n^2)겠지만, 최대 1조 번의 연산이 필요하므로 다른 방법을 찾기로 했다.

- 그 다음으로 떠올린 건 제곱 ㅇㅇ 수를 찾아, 전체 개수에서 빼는 것이다. 여기서 제곱 ㅇㅇ 수는 제곱 ㄴㄴ 수가 아닌 수, 즉 1보다 큰 제곱수로 나누어 떨어지는 수로 정의했다.

- 제곱 ㅇㅇ 수는 어떻게 구할 수 있을까? 위 조건의 경우, 될 수 있는 가장 작은 제곱수는 2의 제곱인 4이다. 특정 범위 내에서 4의 배수의 개수는 어떻게 구할 수 있을까?

- 예를 들어, 1~10 중 4의 배수는 몇 개인가? 4와 8, 두 개다. 이는 (10(max) - 1(min) + 1) / 4와 같아보인다. 가설을 검증하기 위해 다른 예를 들어보자.

- 범위가 4~12라면 어떨까? 범위 내 4의 배수는 4, 8, 12로 3개다. (12 - 4 + 1) / 4 = 2, 이는 틀린 가설임을 알 수 있다.

- mix, max의 값에 따라 개수가 변하는 듯하다. 그렇다면 min / 4 ~ max / 4를 보면 어떨까? 4 / 4 = 1, 12 / 4 = 3. 이 값은 이용할 수 있을 것 같다. (3 - 1 + 1 = 3)

- 만약 min이 3이라면, 3 - 0 + 1 = 4가 된다. min / 4로 소수점을 버리는 대신, 올림을 하면 해결될 것으로 보인다.

- min / 4를 올림(천정 함수 적용), max / 4를 버림(바닥 함수 적용)하면 그 사이의 개수를 구할 수 있다.

- 하지만 예외도 있다. 4의 제곱인 16의 배수는 2의 제곱인 4의 배수와 겹친다. 16이 4의 배수이기 때문이다. 현재 알고리즘은 각 제곱수에 대해, 배수의 개수를 구하므로, 16의 경우는 스킵할 수 있을 것 같다.

- 스킵할 수들의 특징은 무엇인가?

- 10 이하의 정수로 만든 제곱수를 나열해보자. 4, 9, 16, 25, 36, 49, 64, 81. 이들 중 스킵해도 되는 수는 16(4의 배수), 36(4의 배수), 64(4의 배수), 81(9의 배수)이다. 연산해야하는 수는 소수의 제곱수, 스킵해야하는 수는 나머지 제곱수이다.

- 그럼 다음 과정을 생각해볼 수 있다.

 

1. min, max를 입력받는다.

2. count는 min 이상 max 이하 정수의 개수(max - min + 1)로 초기화한다.

3. 반복문을 실행, i를 2의 제곱수부터 시작한다. i * i <= max까지 반복하면 될 것 같다. (최대 1,000,000번 실행)

4. i가 소수인지 판정한다. (최대 10,000번 실행)

5. i가 소수일 경우 i * i의 배수의 개수를 count에서 뺀다. O(1)

6. i가 소수가 아닌 경우 스킵한다.  O(1)

 

여전히 연산량을 러프하게 잡아보면 10,000,000,000(백 억)번으로 많다. 하지만 소수 판정의 연산 횟수가 1부터 10,000까지 증가하는 형식이므로, 실제론 이보다 훨씬 적을 것이다. 프로그램을 짜볼 가치는 있을 듯하다

 

코드

#include <iostream>
#include <cmath>	// floor, ceil 함수 사용

// 소수 판정 함수
bool isPrime(int n) {
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}

	return true;
}

int main() {
	double min, max;
	// min, max 입력
	std::cin >> min >> max;

	// count는 min 이상 max 이하 수의 개수로 시작
	int count = max - min + 1;

	for (int i = 2; i * i <= max; i++) {
		if (isPrime(i)) {
			// min 이상 max 이하인 제곱 ㅇㅇ 수의 개수를 뻼
			count -= (floor(max / (i * i)) - ceil(min / (i * i)) + 1);
		}
	}

	std::cout << count;

	return 0;
}

 

결과

시간 초과로 실패, 즉 방식으론 문제를 해결할 수 없다.

 

추가로 입출력에 대해 체크해본 결과

1~1000의 값이 608이 아닌 558이 나왔다.

이는 중복되는 수가 있었다는 말인데, 아마 제곱수 * 제곱수의 경우가 중복된 것 같다. 예를 들어 9와 49는 모두 소수의 제곱수지만, 9 * 49와 49 * 9는 같으니 count에서 하나의 값이 두 번 제외됐을 것이다.

 

다만 그 이전에 시간 초과가 떴으니, 아예 새로운 풀이 방식을 고민해봐야겠다.

 

+) 위에서 연산량을 러프하게 백 억 번으로 잡았는데, 소수 판정 과정에서 i가 최대 1,000,000까지 가능하므로 실제론 1조 번과 다름 없었다.

---

2. 두 번째 풀이

사고 과정

- DP를 이용해서 1부터 n까지의 제곱 ㄴㄴ 수를 저장하면 풀 수 있어보인다. 하지만 배열 크기가 1조가 될 테고, 제곱 ㄴㄴ 수를 판별하는 로직 또한 필요하므로 다른 방법을 찾아본다.

- 이쯤에서 의문이 하나 든다. 2부터 소수를 모두 곱했을 때, 1조가 넘어가려면 몇 개의 수를 곱해야 할까?

- 계산 결과, 2부터 37까지 곱하면 7,420,738,134,810 (약 7조 4천억)이 된다.

- 2부터 31까지만 나눠보면 될 줄 알았는데, 이보다 큰 소수가 인수일 수도 있음을 깨닫고 포기했다.

- 결국 중요한 건 제곱 ㄴㄴ 수를 어떻게 판별할 수 있을까? 그리고 그건 얼마나 빠르게 가능할까?

- 100만 이하의 모든 소수를 배열로 만들고, 나눗셈만 실행한다면 어떨까?

- ChatGPT에게 물어본 결과 100만 이하 소수의 개수는 78498개이다. 이는 최악의 경우 제곱 ㄴㄴ 수 판정에 78498 번의 연산이 필요하며, 전체 알고리즘은 약 784억 번 실행될 수 있다는 뜻이다. 이조차 상당히 비효율적인 숫자다.

 

- 첫 번째 풀이에서 이어져서, 조금 단순한 방법이지만 '에라토스테네스의 체'를 응용하면 풀릴 것 같다.

- 크기 max - min + 1의 벡터를 만들고, min부터 max까지 집어넣는다.

- 2부터 시작해 제곱의 배수를 지운다. 다시 3에서, 4에서 반복한다.

 

1. min과 max를 입력받는다.

2. min ~ max로 벡터를 만든다.

3. 2부터 시작, 제곱의 배수를 벡터에서 검색, 삭제한다.

 

코드

#include <stdio.h>
#include <vector>
#include <algorithm>

int main() {
	int min, max;
	scanf("%d %d", &min, &max);
	int size = max - min + 1;
	std::vector<int> sieve(size, 0);

	// 체 생성
	for (int i = 0; i < size; i++) {
		sieve[i] = min + i;
	}

	/*for (auto i : sieve) {
		printf("%d, ", i);
	}
	printf("\n\n\n");*/

	// 체에 걸러 삭제
	// 2부터 마지막 원소의 제곱근까지 반복
	for (int i = 2; i * i < max; i++) {
		int p = i * i;
		// f: min에 가장 가까운 p의 배수, l: max에 가장 가까운 p의 배수
		int f = min / p, l = max / p;
		// 범위 내 제곱수 탐색
		for (int j = f; j <= l; j++) {
			auto iter = std::find(sieve.begin(), sieve.end(), p * j);
			if (iter != sieve.end()) {
				sieve.erase(iter);
			}
		}
	}


	/*for (auto i : sieve) {
		printf("%d, ", i);
	}
	printf("\n\n\n");*/

	printf("%d", sieve.size());
}

 

결과

시간 초과를 예상했는데, 틀렸습니다가 나왔다. 사실 디버깅할 때도 1,000,000,000을 넣었을 때 너무 오래 걸려서, 이 방법도 피하기로 했다.

---

3. 세 번째 풀이 (마지막 풀이)

사고 과정

- 아예 러프하게, 처음부터 다시 생각해보자.

- 제곱수를 걸러낸다는 건 유지, 벡터 하나를 새로 파서 제곱수에 해당하면 1 증가시키는 건 어떨까?

- erase 함수나 find 함수를 쓰지 않아도 되니 시간이 절약될 것이고, 제곱 ㄴㄴ수의 개수는 마지막에 벡터 순회로 구할 수 있다.

- 신경쓰이는 건 제곱수를 구해서 곱하는 부분인데... 첫 번째 풀이에서 ceil을 이용한 것처럼, 여기서도 사용해보자.

 

코드

#include <stdio.h>
#include <vector>
#include <cmath>

int main() {
	long long int min, max, count = 0;
	scanf("%lld %lld", &min, &max);
	std::vector<long long int> vec(max - min + 1, 0);

	// 101만 이하일 테니, int로 선언
	int sq = std::sqrt(max);

	for (long long int i = 2; i <= sq; i++) {
		long long int po = i * i;
		// min보다 큰, 가장 작은 po의 배수
		long long int f = std::ceil((double)min / po) * po;
		// f에서 po를 더해가며, 해당하는 벡터를 1씩 증가시킨다.
		while (f <= max) {
			vec[f - min]++;
			f += po;
		}
	}

	// 값이 0인 벡터의 개수를 카운트
	for (auto i : vec) {
		if (i == 0) {
			count++;
		}
	}

	printf("%lld", count);
}

int가 약 21억까지라는 걸 깨닫고, long long int로 코드를 구성했다.

기존엔 i * i를 매 줄마다 계산했는데, 단위가 단위다보니 미리 캐싱해두고 쓰는 걸로 바꿨다. for문 내 조건식도 마찬가지.

 

결과

걱정했던 게 참... 무색하게도, 쉽게 통과했다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/18109385

qjrmsktso2님의 코드. 깔끔하고 이해하기 쉬운 코드가 인상적이다.

 

코드 분석

- MAXP는 max의 제곱근의 ceil이다. 예를 들어 max가 50이면 sqrt(max)는 7.xxx... 일 것이고, MAXP는 8이 된다.

- plist에 capacity를 79,000 할당해뒀다. 100만 이하 소수의 개수가 78,498개이기 때문일까?

- getp는 내가 두 번째 풀이에서 하려던 중복되는 제곱수를 제거하고, 소수의 제곱수만 남기는 과정이다. 2부터 시작해 MAXP 이하의 모든 수에 진행하는데, divisible[i]가 false라면 그 수를 plist에 넣고, 그 수의 배수를 모두 true로 돌린다.

 

이쯤에서 용어를 해석해보자면

p: 나눠볼 제곱수의 제곱근, 2, 3, 5, 7 등의 소수가 속한다.

plist: 나눠볼 p들의 모음

MAXP: max이상 제곱수 중 가장 작은 수의 제곱근. max가 47이라면 MAXP는 49의 제곱근인 7.

getp: max를 토대로 p들을 구하는 과정

divisible: 이미 나눠봤는가?를 저장한 배열

 

정도로 정의할 수 있겠다. 이 코드는 내 첫 번째 풀이와 비교해보는 게 맞는 것 같다.

 

 

내 코드와 비교

1. 소수 판정에 에라토스테네스의 체를 적용했다. 그래서 나보다 훨씬 빠르게 p들을 구할 수 있었다.

2. cnt -= divisible[i - mi] == false;를 통해 같은 값이 두 번 감소되는 일을 방지했다.

3. for문의 증감식에서 i += pp를 함으로써 코드를 좀 더 간결하게 작성했다.

4. using ll = long long을 통해 변수 선언을 더 쉽게 했다. C의 define과 같은 역할인 것 같다.

5. plist를 통해 size는 0인 채 메모리를 할당했다.

---

강평

교수님의 말씀이 떠오른다.

"일단 단순하게 구현해라. 고치는 건 시간 초과가 났을 때면 충분하다."

코드 짜기 전부터 지레 겁먹고 다른 길을 찾아보는 건 내 나쁜 습관인데, 이번에도 압도적인 수의 크기에 놀라 이상한 짓을 했던 것 같다. 무엇보다, 그렇게 짠 코드가 노가다보다 비효율적일 때도 있다는 거다.

 

첫 번째 풀이엔 소수 판정 함수가 엄청난 시간을 잡아먹었다. 이거보단 그냥 중복되는 수도 나눠보는 게 더 빨랐다.

두 번째 풀이엔 find, erase 함수가 들어가며 시간이 더 오래 걸렸다. 특히 find는 그냥 순차 탐색이기에, 호출 시마다 O(n)이란 걸 간과했다. 애초에 틀리기도 했지만.

결국 가장 단순한 생각이 가장 효율적이었다. 이는 다른 문제도 마찬가지일 것이다. 이번 문제는 골드 1티어인데도, 단순하게 접근해야했다. 상위 문제도 크게 다르지 않을 것이다.

 

이번 문제는 첫 번째 풀이엔 티어가 없고, 두 번째 풀이엔 티어가 있다. 지금 비교해보니 12일이나 차이난다. 어렵다고 미뤄두고 틈틈이 고민하며 풀어냈다. 얘보다 심한 문제도 있지만, 여튼 이놈도 오래 걸린 거에 비해 매우 간단하게 풀 수 있었다. 다른 문제들도 복잡하게 생각말고, 일단 단순하게 접근해봐야 겠다.