백준 13909번 : 창문 닫기

---

이번 문제는 n개의 창문이 있고 n명의 사람이 있을 때
n번 째 사람이 n의 배수인 창문을 열고 닫는 문제이다.

이렇게만 보았을 때는 열고 닫는 “행위”를 모두 기록하고 계산해야할 것 같지만 실제로는 그렇지 않다.

나도 이 부분이 헷갈려서 처음에는 아래와 같은 알고리즘을 사용했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws java.io.IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        Arrays.fill(arr, 1);
        arr[0] = 0;

        for (int i = 2; i < n; i++) {
            for (int j = i; j < n; j*=i) {
                if (arr[j] == 0)
                    arr[j] = 1;
                else arr[j] = 0;
            }
        }

        int count = 0;
        for (int i = 0 ; i < arr.length; i++) {
            if (arr[i] == 1)
                count++;
        }
        System.out.println(count);
    }
}

앞서 말한 문제를 그대로 알고리즘으로 옮겨 적은 것이다.
초기 값으로 창문이 모두 열려있을 때를 가정하고
(1의 배수로 시작되어 모든 창문을 열기 때문)
0번 째 인덱스는 없다는 것을 가정한 것이다.

그런데 늦게 보았지만 문제에서 n이 최대 21억까지라는 것이 명시되어있다. 그렇기 때문에 당연히 메모리 초과가 발생한다.

배열의 크기가 한계를 넘었기 때문인데, 이를 해결하기 위해 생각하다가 다시 보니 그냥 단순히 제곱근을 구하는 문제였다.

하지만, 이를 이해하기는 쉽지 않았다.

예를 들어 n이 10인 경우,
첫 번째 사람이 들어오면 모든 창문을 열게되고 (1이라고 한다면)
두 번째 사람부터는 다음과 같다.

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
 1   0   1   0   1   0   1   0   1   0

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
 1   0   0   0   1   1   1   0   0   0

이런식으로 이어진 다면 마지막에는

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
 1   0   0   1   0   0   0   0   1   0

결과적으로 마지막에는 1,4,9번 째 창문만 열려있다.

따라서, 제곱수인 경우만 홀수번 반복해서 상태가 바뀌게 되고 결국 마지막에 열려있게 된다.

그렇다면 문제에서 말하는 열린 창의 개수를 파악하기 위해서는 n의 제곱근을 구하면 간단히 구할 수 있는 문제이다.

결과적으로 정답을 위한 소스코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws java.io.IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        System.out.println((int) Math.sqrt(n));
    }
}

---

이번 문제는 결국 엄청 쉬운 문제였다.
초기에 풀었던 것 역시 답변이 될 수는 있지만 배열의 한계 크기를 넘어서는 숫자가 입력될 수 있기 때문에 엄밀히 따지면 정답이 될 수 없었다.

그런데 수학적 접근 문제를 풀 때마다 느끼는 거지만 수학적 문제에는 특정 패턴이 있고, 그 패턴을 읽어낼 줄 알아야 수월하게 풀린다.
그런 의미에서는 아직 멀었다.