문제 출처

단계별로 풀어보기 > 약수와 소수와 배수 2 > 창문 닫기
https://www.acmicpc.net/problem/13909

문제 설명

N개의 창문과 N명의 사람이 있을 때, i번째 사람은 i배수의 창문을 열려있으면 닫고, 닫혀있으면 연다.
이 때, N명의 사람이 창문을 열고 닫을 때 마지막으로 열려있는 창문의 개수를 구하라.

접근 방법

창문은 i번째의 "배수"일때만 닫히거나 열린다. 그 경우에 창문은 2명의 사람이 지나갈 때마다 원상태로 복구된다.
홀수번 열고 닫히는 창문을 찾아내면 되는데, 이 경우는 제곱수 밖에 없으므로 N번째까지 제곱수를 찾아낸다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class 창문_닫기 {

    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 = 0;

        for(int i = 1; i * i <= N; i++){
            result++;
        }

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

알게된 점

처음에는 그저 직접 배열을 통해 각 배수마다 열리고 닫히는 것을 구현했으나, 이는 조건에 따라서 메모리를 초과한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

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 arr[]= new int[N+1];

        Arrays.fill(arr,0);

        for(int i = 1; i < N+1; i++){
            int num = i;
            while(num <= N){
                arr[num] = arr[num] == 0 ? 1 : 0;
                num+=i;
            }
        }

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

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

제곱수만이 홀수번 열린다는 것을 알게되었다.

시간 복잡도는 O(√N)이다.

문제푼 흔적