[백준] 13909번: 창문 닫기 [C#]

 

 

정수 N이 입력된다면, 1번부터 N번째 사람까지 차례대로 열려있는 창문은 닫고, 닫혀있는 창문은 열고 나간다.

최종적으로 열려있는 창문의 개수를 출력해주면 된다.

 

 

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    { 
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
            StringBuilder sb = new StringBuilder();
 
            int N = int.Parse(reader.ReadLine());
            int cnt = 1;
 
            for (int i = 2; i <= Math.Sqrt(N); i++)
            {
                if (check_square(N))
                    cnt++;
 
            }
            print.WriteLine(cnt);
        }
 
        static bool check_square(int N)
        {
            for (int i = 2; i <= N; i++)
            {
                if ( i*i <= N)
                    return true;
            }
            return false;
        }
    }
}

 

 

어떻게 풀어야 할 지 너무 막막해서 일단 예제의 24를 순서대로 진행 해 보았다.

결과적으로 1, 4, 9, 16 이 남게 되었는데, 이 숫자들의 공통점은 제곱으로 된 수 라는 것이다.

이를 이용해서, 최대 21억회 반복해야 할 것을 N의 제곱근 만큼 반복하는 것으로 줄일 수 있었다.