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

문제

입력

첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.

출력

마지막에 열려 있는 창문의 개수를 출력한다.

문제 링크

 

분석

결론부터 말한다면 N개보다 작거나 같은 제곱수의 개수를 세는 문제이다.

 

 최종적으로는 창문이 열려있는 개수를 세면 된다. 다만 창문과 사람의 수에 볼드처리가 되어있는 것에서 알 수 있듯이. 실제로 각 배수마다 창문을 열고 닫으면 시간초과가 날 것이다. 때문에 최종적으로 창문이 열릴 조건을 찾아내는 것이 핵심이다. 창문이 최종적으로 열려 있으려면 처음에는 닫혀 있으므로 열고닫는 횟수가 홀수면 된다. 각 창문이 열고 닫히는 횟수는 해당하는 수의 약수의 개수와 동일하다.

 

Ex.

4번째 창문을 열고닫는 사람은 1번째, 2번째, 4번째 사람 => 3번 열고 닫으므로 최종적으로는 열린다.

8번째 창문을 열고닫는 사람은 1번째, 2번째, 4번째, 8번째 사람 => 4번 열고 닫으므로 최종적으로는 닫힌다.

 

약수의 개수를 구하기 위해서는 소인수 분해를 이용하면 되지만, 진짜 구해야 할 것은 약수의 정확한 개수가 아니라 약수의 홀짝 판별이다. 약수의 개수가 홀수인 수는 제곱수들이다.
따라서 이 문제는 최종적으로는 제곱수의 개수를 세는 문제이다.

 

풀이

핵심코드

for (ull i = 1; i * i <= N; i++) cnt++;

 

전체코드

#include<iostream>

using ull = unsigned long long int;

int main(int argc, char** argv)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL); std::cout.tie(NULL);

	ull N, cnt;
	std::cin >> N;
	cnt = 0;
	for (ull i = 1; i * i <= N; i++) cnt++;
	std::cout << cnt;

	return EXIT_SUCCESS;
}