문제설명

오늘도 1일 1코테를 실천 중이었는데 무언가 문제가 발생했다.

나에게 고통을 주었던 문제는 다음과 같다

[Silver V] 창문 닫기

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

문제 내용

처음에는 굉장히 단순하게 생각했다. for문을 돌려서 계산을 해보기도 했고 HashMap을 사용해서 해보기도 했다.

import java.io.*;

public class Q13909 {
  public static void main (String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());

    int[] window = new int[N+1];

    int result = 0;

    for (int i=1; i<N+1; i++) {
      for (int j=i; j<N+1; j += i) {
        if (window[j] == 1) {
          window[j] = 0;
        }
        else if (window[j] == 0) {
          window[j] = 1;
        }
      }
    }
    
    for (int i=1; i<N+1; i++) {
      if (window[i] == 1) {
        result += 1;
      }
    }

    bw.write(String.valueOf(result));
    bw.flush();
    bw.close();
  }
}

import java.io.*;
import java.util.*;

public class Q13909var2 {
  public static void main (String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());

    HashMap<Integer, Integer> window = new HashMap<>();

    int result = 0;

    for (int i=1; i<=N; i++) {
      window.put(i, 0);
    }

    for (int i=1; i<=N; i++) {
      for (int j=i; j<=N; j+=i) {
        window.put(j, 1-window.get(j));
      }
    }

    for (int i=1; i<=N; i++) {
      if (window.get(i) == 1) {
        result += 1;
      }
    }

    bw.write(String.valueOf(result));
    bw.flush();
    bw.close();
  }
}

그런데 생각을 해보면 해당 문제는 Hash를 사용한다고 해서 탐색에서 이득을 볼리가 없다고 생각했고, 도대체 어떻게 풀어야할지 의문이었다.

문제 해결

저 메모리 초과가 계속해서 발생했고, 결국 돌아가는 코드만을 이용해서 출력을 하나씩 뽑기로 했다.

열심히 하나씩 출력을 뱉어내던 중 특이한 규칙을 발생하게 되었다

1-1
2-1
3-1
4-2
5-2
6-2
7-2
8-2
9-3

왼쪽이 입력이고 오른쪽은 출력이다
그렇다.
이상하게 값들이 제곱근을 만날때마다 1씩 커지는 것이었다

순서대로 설명해보겠다

1
1 1 / 1 0
1 1 1 / 1 0 1 / 1 0 0
1 1 1 1 / 1 0 1 0 / 1 0 0 0 / 1 0 0 1

최종 값에 집중하면, 한가지 규칙을 알 수 있게 된다
그 전 값들은 유지가 되고 맨 오른쪽에 해당하는 창문만 1로 udpate되는 것이다..!

이는 완전제곱수의 경우에 관련이 있는데 완전제곱수들은 약수로 홀수값을 갖고 있기 때문이다

즉, 자연스레 완전제곱수를 만날 때마다 열린 창문의 수가 1씩 증가하는 값을 얻을 수 있는 것이다

그렇게 완성된 코드는 아래와 같다

더이상 for문을 중첩시키지 않아도 되고, Hash를 하지 않아도 되고, binarySearch를 사용하지 않아도 좋다

import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    int result = (int) Math.sqrt(N);

    bw.write(result + "\n");
    bw.flush();
    bw.close();
  }
}

결론

문제를 보다 정확히 이해하는 과정이 필요하다
특히, 입력에 따른 결과를 한번 미리 적으며 이를 이해하는 과정 또한 필수적이다