[백준] 13909 _ 창문 닫기 (Java)

정답과 결론은 맨 아래에-!!

예를 들어 창문이 3개 있다면 3명의 사람이 한명씩 돌아가면서 창문을 여닫는다.
그리고 최종적으로 열려있는 창문의 개수를 구하는 문제이다.

문제 이해

[ 조건 ]
1. 처음엔 창문이 모두 닫혀있는 상태이다.
2. 사람은 각자 사람1, 사람2, 사람3이라는 번호를 가지고 있다.
3. 창문 3개도 1,2,3의 번호를 가지고 있다.
4. 창문이 열려있으면 닫고, 닫혀있으면 여는 행동을 토글이라고 하자.
5. 창문의 상태 : 0일 때 닫힘 / 1일 때 열림

[ 해석 ]

1. 1번인 사람은 자신의 번호인 1의 배수인 번호의 창문만 토글 한다.
   ex) 1의 배수는 1,2,3 --> 모든 창문을 토글함 = 모든 창문이 열림
   창문 상태 : 000 --> 111

2. 2번인 사람은 자신의 번호인 2의 배수인 번호의 창문만 토글한다.
   ex) 2의 배수 2번 창문만 토글
   창문 상태 : 111 -> 101

3. 3번인 사람은 3의 배수인 3번 창문만 토글한다.
   ex) 3의 배수 3번 창문만 토글
   창문 상태 101 --> 100

= 최종적으로 열려있는 창문은 1번 창문이다.

---

[ 결론 ]
아래의 토글 과정을 보면 창문이 열려 있는 경우는 홀수번째이다.
열고 - 닫고 - 열고 - 닫고 - 열고
따라서 약수가 홀수일 때 창문은 열려있다.
=> 이 말은 약수를 홀수개 가지고 있는 창문을 찾으면 된다.

입출력 형식

숫자 n이 주어지면 창문의 수도 n개, 사람의 수도 n명이다.
출력은 열려있는 창문의 개수 ( = 약수가 홀수개 있는 숫자의 개수 )를 출력하면 된다.

코드 1 (메모리 초과)

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

// 메모리 초과
public class App {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    boolean[] array = new boolean[n + 1];
    int result = 0;

    // i = 사람   j = 창문
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (j % i == 0) {
          array[j] = !array[j];
        }
      }
    }

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

    System.out.println(result);
  }
}

약수가 홀수의 개수인 숫자를 구하면 된다고 알게되기 전에는 boolean타입의 배열을 만들어서 토글하는 방식을 사용했다.
for문만을 이용해서 돌리다보니 숫자가 최대 21억까지 올라가면서 메모리 초과가 발생했다.

코드 2 (정답 코드)

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

public class App2 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    int count = 0;

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

    System.out.println(count);
  }
}

원리대로 풀어보니 코드가 매우 짧아졌다.
위에 말한대로 약수를 (1 포함) 홀수개로 가지고 있는 숫자는 어떠한 숫자의 제곱일 때이다.
1의 제곱 = 1 --> 1 (1)
2의 제곱 = 4 --> 1, 2, 4 (3)
3의 제곱 = 9 --> 1, 3, 9 (3)
4의 제곱 = 16 --> 1, 2, 4, 8, 16 (5)
...

따라서 n이 주어졌을 때 해당 숫자만큼 for문을 돌리며 n보다 작거나 같은 제곱의 개수 를 구하면 된다.