[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의 범위를 보면 절대로 for문으로 0101 하는 문제가 아니다.

N 안에 수 x의 약수의 개수가 짝수면 닫혀있는거고 홀수면 열려있다.

약수의 개수 구하기 알고리즘을 찾아보았다.

number의 약수 중 하나가 i 라고 했을 때, 다른 약수는 number / i 가 되므로 하나의 약수를 알면 다른 하나의 존재가 보장된다.
이 경우 O(√n)의 시간복잡도가 보장된다.

for(int i = 1; i * i <= number; i++)
{
	if(i * i == number) cnt++;
    else if(number % i == 0) cnt += 2;
}

n까지 수 각각에 대해 약수의 개수를 구하고, 홀수라면 cnt++

를 해서 총 cnt를 구하면 그것이 열려있는 창문의 수이다.

처음 코드

namespace SongE
{
    public class Program
    {
        static int DivCount(int n)
        {
            int num = n;
            int cnt = 0;

            for(int i = 1; i * i <= num; i++)
            {
                if (i * i == num) cnt++;
                else if (num % i == 0) cnt += 2;
            }

            return cnt;
        }
        static void Main(string[] args)
        {
            using var input = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(input.ReadLine());
            int cnt = 0;

            for(int i = 1; i <= n; i++)
            {
                if (DivCount(i) % 2 != 0) cnt++;
            }

            print.Write(cnt);
            
        }
    }
}

시간초과났습니다.
역시 2,100,000,000

찾아보니까 n의 제곱근일때는 창문이 열려있다네요.

두번째 코드

namespace SongE
{
    public class Program
    {
        static void Main(string[] args)
        {
            using var input = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int n = int.Parse(input.ReadLine());
            int cnt = 0;

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

            print.Write(cnt);  
        }
    }
}