[c/c++] 백준 13909(Silver 5)

🔨 문제

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

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

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

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

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

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

🔨 해결방법

일단 창문은 열고 닫히는 두 가지 액션이 있다. 순서대로 위치에 해당하는 값의 배수의 값만 열려있으면 닫고, 닫혀있으면 열면 된다.

하지만 해당 문제는 배수를 이용하기 때문에 어찌됐든 약수의 개수만큼 열리거나 닫힐 것이다. 문제에서는 창문이 열린 개수를 세어야 하기 때문에 약수의 개수가 홀수인 경우만 카운트해주면 문제를 해결할 수 있다.

예를 들어서 N=10인 경우에, 1,4,9만 약수의 개수가 홀수이다. 이 수들만 결과적으로 창문이 열린 상태가 된다. 이 수들의 특징은 제곱수라는 것이다. 이를 이용하여 코드를 작성하면 된다.

🔨 코드

#include <iostream>
using namespace std;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int p=0,cnt=0;
    cin >> p;

    for(int i=1;i*i<=p;i++){
        cnt++;
    }
    cout << cnt;

    return 0;
}