📌 문제

[13909] 창문 닫기

서강대학교 컴퓨터공학과 실습실 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+1인 boolean 타입 배열 window[]에 저장한다. (열림 : true / 닫힘 : false) 이후 n까지의 배수에 따라 창문을 열거나 닫아야 하므로 이중 for문을 사용하여 (i ~ n * 1 ~ n/i)에 해당하는 창문을 열거나 닫아준다. boolean 타입이므로 논리 부정 연산자 !를 사용하여 값을 바꿔주면 된다. 반복문이 종료되면 최종 요소의 값이 true인 경우만 카운트해서 출력한다.

아래 코드를 이클립스에서 실행하면 제대로 된 답이 나오는데, 백준에 제출하면 메모리 초과가 뜬다! 떠도 시간 초과가 뜰 거라고 생각했는데 메모리 초과는 처음이라 당황해서 문제를 보니,, 메모리 제한이 64MB였다,, 아무래도 배열을 쓰면 안될 것 같은 느낌,,

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());
		boolean[] window = new boolean[n+1];
		
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n/i;j++) {
				window[i*j] = !window[i*j];
			}
		}
		
		int cnt = 0;
		for(int i=1;i<=n;i++) {
			if(window[i]) cnt++;
		}
		bw.write(cnt + "");
		
		br.close();
		bw.close();
	}
}

✅ 위 코드를 사용하여 마지막에 열려있는 창문들의 인덱스를 찍어봤는데 놀랍게도 1의 제곱, 2의 제곱, 3의 제곱, ... √n의 제곱 이라는 규칙이 있었다! 이 규칙을 사용하면 배열 없이 Math.sqrt(n) 메서드를 사용하면 간단하게 문제를 해결할 수 있다!

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 cnt = 0;
		for(int i=1;i<=Math.sqrt(n);i++) {
			cnt++;
		}
		bw.write(cnt + "");
		
		br.close();
		bw.close();
	}
}

➕ 근데 어차피 1부터 Math.sqrt(n)까지의 개수가 Math.sqrt(n)의 값과 똑같은데 굳이 for문을 안돌려도 되지 않나,, 라는 생각이 제출하고 나서야 들었다,, ㅎㅎ

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());
		bw.write((int)Math.sqrt(n) + "");
		
		br.close();
		bw.close();
	}
}

(처음에 이전 문제에 사용했던 크기가 10000001인 배열을 안지우고 코드를 제출해서 메모리 초과가 떴나 했는데,, 그냥 첫 문제의 배열 그 자체가 문제였던 걸로 ~^^)