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

https://www.acmicpc.net/problem/13909

문제

---

서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.  2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.

예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,

1. 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2. 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3. 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.

 

입력

---

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

 

출력

---

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

 

문제 풀이

---

수학 문제.

 

창문 번호가 소수인 창문은 1번째 사람에 의해 열리고, 소수번째 사람에 의해 닫힌다.

창문번호가 소수가 아닌 창문에 대해 확인해보자. 창문 번호에 대해 약수인 사람만이 열고 닫을 수 있다. 첫번째 약수 번호인 사람에 의해 창문이 열리고, 두번째 약수 번호인 사람에 의해 창문이 닫힌다. 세번째 약수 번호인 사람에 의해 창문이 열리고, 네번째 약수 번호인 사람에 의해 닫힌다. 즉, 약수의 개수가 홀수이면 마지막에 창문이 열리고, 약수의 개수가 홀수이면 마지막에 창문이 닫힌다.

N이 i에 의해 나누어지면 N / i에 의해서도 나누어지므로, 약수의 개수가 짝수이다. 단, i가 N / i와 같아지는 경우가 있는 경우, 즉 어떤 수에 대해 제곱수 일 때 약수의 개수가 홀수가 된다.

그러므로 문제를 다시 정의하면 N까지의 수 중 제곱수의 개수를 구하는 문제가 된다.

이는 간단하게 sqrt(N)이 되고, 이것이 정답이다.

 

아래는 코드.

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

int main()
{
	int N;
	cin >> N;
	int answer = sqrt(N);
	cout << answer << "\n";
	return 0;
}