[C++] 백준 13909. 창문 닫기

문제

N명의 학생이 N개의 창문을 열고 닫을건데,
N의 배수번째 창문이 열려있으면 닫고, 닫혀있으면 여는 식이다.
처음에 모든 창문은 닫혀있고, 1번 학생은 1부터 N까지 모든 문을 연다.

N의 범위는 1부터 2,100,000,000이고,
마지막에 열려 있는 창문의 개수를 출력하는 문제이다.

시도

배수번째 창문을 거쳐간다길래 별 생각 없이 vector<bool> v(n+1, true)를 선언해서 풀었더니 메모리초과(64MB)가 났다.

bool은 1bit인데 N이 21억이면
2,100,000,000÷8 ≈ 262,500,000Byte ≈ 250MB로 메모리 제한을 훌쩍 넘긴다.

메모리 초과 코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<bool> v(n + 1, true);

	for (int i = 2; i <= n; i += i) {
		v[i] = !v[i];
	}

	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (v[i]) cnt++;
	}
	cout << cnt;

	return 0;
}

풀이

다른 방법을 생각해보다가,
너무 문제에서 낚으려는 방향대로 생각했나 싶어 약수를 떠올려봤다.
어떤 수의 약수의 개수가 홀수이면 마지막에 열린 상태가 된다.
약수의 개수가 홀수이려면 그 값의 제곱근이 정수면 된다.
1, 4, 9, 16 처럼 완전제곱수이면 되는거다.

for문으로 2부터 n까지 돌면서 제곱근이 정수인지 판별하는 방법을 생각했다가
거꾸로, 2부터 n의 제곱근까지 돌면서 그것의 제곱이 n보다 작은 경우에만 카운트하는 방법으로 풀었다.

코드

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int n, cnt = 0;
	cin >> n;
	
	for (int i = 1; i <= sqrt(n); i++) {
		if (i * i > n) break;
		cnt++;
	}
	cout << cnt;

	return 0;
}

채점