[Java] 백준알고리즘 #13909 창문 닫기

백준알고리즘 #13909 창문 닫기

 

첫번째 사람부터 n번째 사람까지 차례대로 창문을 열고 닫을 때, 마지막에 열려 있는 창문의 개수를 구하는 문제.

단순히 반복문을 사용해 1부터 n까지 차례대로 닫혀있다면(0이면) 1로, 열려있으면(1이면) 0으로 바꿔준 후 1인 개수를 체크하는 식으로 풀어보았다.

 

// 해설참조 : sehyeok.tistory.com 

import java.util.Scanner;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ary = new int[n];
        int count = 0;
        for (int i = 1; i <= n; i++) {
            int j = 1;
            while (i * j <= n) {
                if (ary[i * j - 1] == 0) {
                    ary[i * j - 1] = 1;
                    count++;

                } else {
                    ary[i * j - 1] = 0;
                    count--;
                }
                j++;
            }
        }
        System.out.println(count);
        sc.close();
    }
}

 

결과는 실패.

n에 큰 수 (2,100,000,000 등) 가 들어가는 경우 메모리가 초과되어

java.lang.OutOfMemoryError: Java heap space 에러가 발생했다.

서버를 실행할 때, 힙 공간에 메모리를 할당하게 되는데 이 힙 공간의 총 용량보다 넘쳐서 발생하는 에러라고 한다.

 

때문에 다른 방식으로 문제를 해결해보자.

 

n까지의 수가 있을 때 문제처럼 1부터 n까지 각 배수의 창문을 열고 닫기를 반복한다면,

x번째의 창문의 약수가 짝수일 때는 닫히고, 홀수일 때는 열릴 것이다.

10인 경우

1번째  : 1,1,1,1,1,1,1,1,1,1

2번째  : 1,0,1,0,1,0,1,0,1,0

3번째  : 1,0,0,0,1,1,1,0,0,0

4번째  : 1,0,0,1,1,1,1,1,0,0

5번째  : 1,0,0,1,0,1,1,1,0,1

6번째  : 1,0,0,1,0,0,1,1,0,1

7번째  : 1,0,0,1,0,0,0,1,0,1

8번째  : 1,0,0,1,0,0,0,0,0,1

9번째  : 1,0,0,1,0,0,0,0,1,1

10번째 : 1,0,0,1,0,0,0,0,1,0

 

열려 있는 창문은 1,4,9번째 창문이라는 것을 알 수 있다.

즉 각 창문의 약수가 홀수개인 경우에만 창문이 열려 있다는 것인데, 이는 제곱수의 경우에 해당한다.

어떤 수의 약수는 필히 2개의 쌍을 가지므로 짝수개의 약수를 가지지만, 제곱수는 홀수개의 약수를 가진다

(2,2) (3,3) 등으로 중복되는 쌍이 생기기 때문.

 

이를 이용하여 n개의 창문이 있다고 할 때, n보다 작은 제곱수 중 가장 큰 수를 구하면 된다.

코드 또한 다음과 같이 아주 간단하게 작성할 수 있다.

 

// 해설참조 : sehyeok.tistory.com 

import java.util.Scanner;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

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

        System.out.println(i - 1);

        sc.close();
    }
}

 

i =1부터 시작하여 차례로 증가하면서 n보다 작은 제곱수를 구한다.

i의 제곱이 n을 초과한다면, 이 i에서 1을 뺀 것을 출력해주면 완성.