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

[ 문제 ]

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

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

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

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

 

[ 코드 ]

1. 맞은 코드

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

int N = int.Parse(sr.ReadLine());
int count = 0;
for (int i = 1; i * i <= N; i++)
{
    count++;
}

sw.Write(count);
sw.Flush();
sw.Close();
sr.Close();

 

2. 메모리 초과 코드(배열 사용)

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

int n = int.Parse(sr.ReadLine());
int[] arr = new int[n];
Array.Fill(arr, 0);

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= n; j++)
    {
        if (j % i == 0)
        {
            arr[j - 1] = 1 - arr[j - 1];
        }
    }
}

int sum = arr.Sum();
sw.Write(sum);
sw.Flush();
sw.Close();
sr.Close();

 

[ 풀이 ]

약수가 홀수일 때 열린 창문의 개수가 올라간다.

1: 1개 (1) 2: 2개 (1, 2) 3: 2개 (1, 3) 4: 3개 (1, 2, 4) 5: 2개 (1, 5) 6: 4개 (1, 2, 3, 6) 7: 2개 (1, 7) 8: 4개 (1, 2, 4, 8) 9: 3개 (1, 3, 9) 10: 4개 (1, 2, 5, 10) 11: 2개 (1, 11) 12: 6개 (1, 2, 3, 4, 6, 12) 13: 2개 (1, 13) 14: 4개 (1, 2, 7, 14) 15: 4개 (1, 3, 5, 15) 16: 5개 (1, 2, 4, 8, 16)

 

3명이 있다고 하면 그 안에 제곱수가 1개 포함되어 있기 때문에 1,

16명이 있다고 하면 그 안에 제곱수가 4개(자기자신 포함) 포함되어 있기 때문에 4이다. 

 

각 창문은 그 창문 번호의 약수인 사람에 의해 상태가 바뀐다. 이때, 약수의 개수가 홀수인 경우에만 최종적으로 열려있는 상태가 된다. 그렇기 때문에  제곱수의 유무로 열린 창문의 수를 셀 수 있다.

 

[ 실행화면 ]

case: 1

 

 

 

 

---

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

13909번: 창문 닫기