YUMIN KIM

문제

메모리초과

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

public class boj13909{
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = 0;
        int ans = 0;
        
        n = Integer.parseInt(br.readLine());

        boolean[] arr = new boolean[n+1];
        arr[0] = true;

        //열려있다. -> 소수 -> false  닫혀있다 -> true
        for(int i = 2; i < n+1; i++ ){
            int j = 1;
            
                while(i * j <= n){
                    if(arr[i * j] == true) arr[i * j] = false;
                    else arr[i * j] = true;
                    j++;
            }
        }
        for(int i = 1; i < n+1; i++){
            if(!arr[i]){
                ans ++;
            }

        }
        System.out.println(ans);
    }
}

음… String으로 받아오는게 커서 그런가? Scanner를 통해 int로 받아올까? 아니지… 아무리 생각해도 배열이 문제다. 안 그래도 에라토스테네스의 체는 메모리 문제가 있는데다가 20억가까이를 배열에 할당하는 건 불가능이다.

놀랍게도 위에 코드로 2에서 25까지 계속 실행시키다 보면 규칙성을 발견할 수 있다.

3 1
4 2
5 2
6 2
7 2
8 2
9 3
….
25 5

규칙은 바로 숫자 n이 주어졌을 경우, 열린 창문의 수는 n의 제곱근의 정수값이다.

다시 풀이를 고쳐보면,

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

public class boj13909{
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int t = (int) Math.sqrt(n);
        
        System.out.println(t);

    }
}

결과

참고로 백준에 제출할 때 소스 코드의 class 명은 무조건 Main으로 바꿔야 한다. 잊지 말기를

이 문제를 끝으로 약수/배수의 대표문제는 다 풀었다!