[JAVA] 백준 13909. 창문 닫기

이 글은 읽는데 약 3분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

서강대학교 컴퓨터공학과 실습실 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개 이다.

입력

첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다.

출력

마지막에 열려 있는 창문의 개수를 출력한다.

풀이

단순한 방법으로 풀려면 창문의 개수만큼 배열을 선언하고 그만큼 반복문을 돌면서 창문의 상태를 변경하면 되겠지만 안된다. 입력 N의 최대값이 무려 21억으로 이 길이의 배열을 선언하면 메모리 초과가 뜨고만다. 이런 이유도 있지만 약간 생각을 하면 단순히 계산만으로 바로 답이 나온다.

for(int N=1; N<=20; N++){
    boolean[] windows = new boolean[N+1];
    for(int i=1; i<=N; i++){
        int pos = i;
        while(pos <= windows.length-1){
            windows[pos] = !windows[pos];
            pos += i;
        }
    }

    int cnt = 0;
    for(boolean w : windows){
        if(w) cnt++;
    }

    sb.append(N + ": " + cnt);
    sb.append("\n");
}

먼저 이런식으로 20개 정도에 대해서만 결과를 시뮬레이션 해본다. 어차피 시뮬레이션이므로 그냥 배열을 이용하여서 단순무식한 방법으로 돌려봤다.

결과는 다음과 같다:

1: 1
2: 1
3: 1
4: 2
5: 2
6: 2
7: 2
8: 2
9: 3
10: 3
11: 3
12: 3
13: 3
14: 3
15: 3
16: 4
17: 4
18: 4
19: 4
20: 4

N이 4, 9, 16일 때마다 마지막에 열린 창문의 개수가 1씩 증가하는 것을 알 수 있다. 즉, N이 완전제곱수이면 그 지점부터 마지막에 열린 창문의 개수가 1씩 증가한다는 뜻이다.

또한 \(\sqrt {9} = 3\)이고, \(\sqrt {10} = 3.162…\)처럼 다음 완전제곱수 전 까지의 범위의 수의 제곱근의 정수 부분도 똑같이 3이다.

이를 정리하면 마지막에 열린 창문의 개수는 곧 \(\sqrt {N}\)의 소수점을 버린 값과 같다는 것이 된다.

int N = Integer.parseInt(br.readLine());
sb.append((int)Math.sqrt(N));
System.out.println(sb.toString());

이렇게 간단히 풀린다!

댓글