반응형
<문제 소개>
<소스 코드>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <unordered_map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
int count = 0;
// 약수의 갯수 -> 짝수 : 0, 홀수 : 1
// 제곱수의 약수의 갯수 -> 홀수 -> 제곱수의 갯수 = 열린 창문의 갯수
for (int i = 1; i <= sqrt(N); i++) count++;
cout << count;
return 0;
}<풀이과정>
n번째 창문의 열리고 닫히는 것의 판단은 n번째 사람까지의 행동에 의해서 결정된다.
예를들어, 1번 창문은 1번 사람이 처음에 열고 그 이후로는 건들 수 없다. 2번 창문 또한 2번 사람까지만 건들 수 있다.
이를 통해 n번째 창문은 n의 약수에 해당되는 번호의 사람에 의해서 결정된다는 것을 알 수 있다.
처음엔 창문이 모두 닫혀있으므로 n의 약수가 짝수개라면 최종적으로 n번째 창문은 닫혀있을 것이고, 약수가 홀수개라면 최종적으로 n번째 창문이 열려있을 것이다.
그러므로 약수가 홀수개인 경우를 찾으면 되는데 생각해보면 약수가 홀수가 되는 경우는 4,9와 같은 제곱수만이 해당된다. 따라서 제곱수의 갯수를 찾으면 된다.
1. N을 입력받고 열린 창문의 갯수 count를 선언
2. N의 제곱근보다 작은 수들의 제곱수는 모두 N보다 작은 제곱수이므로 1부터 N의 제곱근까지의 갯수가 총 제곱수의 갯수가 되고 이는 열린 창문의 갯수가 된다.
3. 반복이 끝난 뒤 count를 출력해준다.
<코멘트>
메모리초과, 시간초과를 안 내는 것이 관건!
제곱수까지 생각해내는 것이 어려웠다.
<제출결과>
