[C#] 13909번: 창문 닫기

목차

---

백준 단계별로 풀어보기

25.11.13

15단계: 약수, 배수와 소수 2

13909번: 창문 닫기

문제 링크 : https://www.acmicpc.net/problem/13909

 

문제를 풀기 위해 알아야 할 개념

>> N번 창문이 열렸는지, 닫혔는지 아는 방법

: 1부터 N까지 각 사람은 본인의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.

ex) 12번째 창문을 보자.

• 1번째 사람이 연다.
• 2번째 사람이 닫는다.
• 3번째 사람이 연다.
• 4번째 사람이 닫는다.
• 6번째 사람이 연다.
• 12번째 사람이 닫는다.

--> 12의 약수에 해당하는 사람이 창문을 열고 닫는다.

▶ 약수의 개수가 홀수인 번호의 창문이 최종적으로 열려 있을 것이다. 그리고 약수의 개수가 홀수인 번호는 제곱수 밖에 없다. 즉, N이 제곱수가 아니라면 창문은 닫혀있고 N이 제곱수라면 창문은 열려있다.

 

문제 풀이

>> 오답노트

: 실제로 모든 창문의 상태를 구했더니 메모리 초과로 실패했다.

--> bool 타입 배열로 창문을 표현하고, 이중 for 반복문을 통해 창문을 열고 닫음.

 

- 작성한 코드

<hide/>
using System.IO;
using System.Linq;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());

        int n = int.Parse(sr.ReadLine());

        bool[] window = Enumerable.Repeat(true, n + 1).ToArray();
        window[0] = false;

        for (int i = 2; i <= n; i++)
        {
            for (int j = i; j <= n; j += i)
            {
                window[j] = !window[j];
            }
        }

        int result = 0;
        for (int i = 1; i <= n; i++)
        {
            if (window[i])
                result++;
        }

        sw.Write(result);
    }
}

 

>> 최종 수정

: 최종적으로 열려 있는 창문은 제곱수 뿐이라는 것을 활용하자.

--> 주어진 입력값 N에 대하여 √N 의 정수 부분만 구하면 열려있는 창문의 개수를 알 수 있다.

1. StreamReader로 입력값을 받아 int값으로 변환하여 창문의 개수와 사람의 수를 담을 변수 n 에 담는다.
2. StreamWriter로 Math.Sqrt() 함수를 활용하여 √n 을 구하고, int값으로 형변환하여 출력한다.

 

정답 코드

using System.IO;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());

        int n = int.Parse(sr.ReadLine());
        
        sw.Write((int)Math.Sqrt(n));
    }
}