학습용 공간

1. Bottom-Up

import java.util.Scanner;

public class Main {
    static long mod = 1000000009;
    static long[][] A = new long[100000+1][4]; // n을 1, 2, 3의 합으로 나타내는 방법의 수를 저장하는 배열
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        add123();
        for (int i=0;i<cnt;i++) {
            int num = sc.nextInt();
            System.out.println((A[num][1] + A[num][2] + A[num][3])%mod);
        }
    }

    public static void add123() {
        // Bottom-UP 방식
        // A[i][j] = i를 1, 2, 3의 합으로 만드는 방법의수, j는 마지막으로 더한 수
        // 점화식 : A[n] = A[n][1] + A[n][2] + A[n][3]
        // A[n][1] = A[n-1][2] + A[n-1][3]
        // A[n][2] = A[n-2][1] + A[n-2][3]
        // A[n][3] = A[n-3][1] + A[n-3][2]

        // 예외처리 (중복 피하기 위함)
        A[1][1] = 1%mod;
        A[2][2] = 1%mod;
        A[3][1] = (A[2][2] + A[2][3])%mod;
        A[3][2] = (A[1][1] + A[1][3])%mod;
        A[3][3] = 1%mod;
        for (int i=4;i<100001;i++) {
            A[i][1] = A[i-1][2] + A[i-1][3]; // 마지막에 1을 더해서 n을 만드는 경우의 수
            A[i][2] = A[i-2][1] + A[i-2][3]; // 마지막에 2을 더해서 n을 만드는 경우의 수
            A[i][3] = A[i-3][1] + A[i-3][2]; // 마지막에 3을 더해서 n을 만드는 경우의 수
            A[i][1] %= mod;
            A[i][2] %= mod;
            A[i][3] %= mod;
        }
    }
}

2. Top-Down : 시간초과 발생.. 해결 방법 찾지 못함 ㅠ

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

public class Main {
    static int[][] A; // n을 1, 2, 3의 합으로 나타내는 방법의 수를 저장하는 배열
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        for (int i=0;i<cnt;i++) {
            int num = sc.nextInt();
            A = new int[num+1][4];
            System.out.println(add123(num));
        }
    }

    public static int add123(int n) {
        // Top-Down 방식
        // A[i][j] = i를 1, 2, 3의 합으로 만드는 방법의수, j는 마지막으로 더한 수
        // 점화식 : A[n] = A[n][1] + A[n][2] + A[n][3]
        // A[n][1] = A[n-1][2] + A[n-1][3]
        // A[n][2] = A[n-2][1] + A[n-2][3]
        // A[n][3] = A[n-3][1] + A[n-3][2]

        // 예외처리 (중복 피하기 위함)
        if (n < 2) {
            A[n][1] = 1;
            return 1;
        }
        if (A[n-1][1] == 0 && A[n-1][2] == 0 && A[n-1][3] == 0) {
            add123(n-1);
        }
        if (n == 2) {
            A[n][2] = 1;
            return 2;
        }
        if (n == 3) {
            A[n][1] = A[n-1][2] + A[n-1][3];
            A[n][2] = A[n-2][1] + A[n-2][3];
            A[n][3] = 1;
            return 3;
        }
        A[n][1] = A[n-1][2] + A[n-1][3]; // 마지막에 1을 더해서 n을 만드는 경우의 수
        A[n][2] = A[n-2][1] + A[n-2][3]; // 마지막에 2을 더해서 n을 만드는 경우의 수
        A[n][3] = A[n-3][1] + A[n-3][2]; // 마지막에 3을 더해서 n을 만드는 경우의 수
        int temp = (A[n][1] + A[n][2] + A[n][3])%1000000009;
        return temp;
    }
}

1. Top-Down

import java.util.*;

public class Main {
    static int[] A; // 인덱스 개수의 카드를 구입하는데 든 최소 비용
    static int[] P; // 인덱스 개의 카드를 포함하는 카드팩의 가격
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int card = sc.nextInt();
        A = new int[card+1];
        P = new int[card+1];
        for (int i=1;i<card+1;i++) {
            P[i] = sc.nextInt();
            A[i] = -1;
        }
        System.out.println(minPrice(card));
    }

    public static int minPrice(int num) {
        // Top-Down 방식
        // A[n] = n개의 카드를 구매하는 최소 비용, P[i] = i개의 카드를 포함하는 카드팩의 가격
        // 점화식 : A[n] = min(A[n-i] + P[i])
        if (num < 1) {
            return 0;
        }
        if (A[num-1] == -1) {
            A[num-1] = minPrice(num-1);
        }
        for (int i=1;i<num+1;i++) {
            if (A[num]==-1 || A[num] > A[num-i] + P[i]) {
                A[num] = A[num-i] + P[i];
            }
        }
        return A[num];
    }
}

2. Bottom-Up

import java.util.*;

public class Main {
    static int[] A; // 인덱스 개수의 카드를 구입하는데 든 최소 비용
    static int[] P; // 인덱스 개의 카드를 포함하는 카드팩의 가격
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int card = sc.nextInt();
        A = new int[card+1];
        P = new int[card+1];
        for (int i=1;i<card+1;i++) {
            P[i] = sc.nextInt();
            A[i] = -1;
        }
        System.out.println(minPrice(card));
    }

    public static int minPrice(int num) {
        // Bottom-Up 방식
        // A[n] = n개의 카드를 구매하는 최소 비용, P[i] = i개의 카드를 포함하는 카드팩의 가격
        // 점화식 : A[n] = min(A[n-i] + P[i])
        for (int i=1;i<num+1;i++) {
            for (int j=1;j<i+1;j++) {
                if (A[i]==-1 || A[i] > A[i-j] + P[j]) {
                    A[i] = A[i-j] + P[j];
                }
            }
        }
        return A[num];
    }
}

해당 문제를 위한 알고리즘을 해결해야 하는 부분 문제의 수가 n(카드 개수)개, 

각 부분 문제를 해결하기 위해 총 n개의 수를 비교해서 그 중 최대값을 구해야 하므로 부분 문제당 O(n)의 시간이 소요된다.

결국 O(n^2)의 시간복잡도를 갖는다.

1. Top-Down 방식

import java.util.*;

public class Main {
    static int[] A; // 해당 인덱스 개수의 카드를 구매하는 최대 금액
    static int[] P; // 인덱스 개수의 카드를 포함하는 카드팩의 가격
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cardNum = sc.nextInt();
        P = new int[cardNum+1];
        A = new int[cardNum+1];
        for (int i=1;i<cardNum+1;i++) {
            P[i] = sc.nextInt(); // 각 카드 팩의 가격 받아오기
        }
        System.out.println(maxPrice(cardNum));
    }

    static int maxPrice(int num) {
        // Top-Down 방식
        // A[n] = n개의 카드를 구매하는 최대 금액, P[i] = i개의 카드를 포함하는 카드팩의 가격
        // 점화식 : A[n] = max(A[n-1] + p[i])
        if (num < 1) {
            return A[num];
        }
        if (A[num-1] == 0) {
            A[num-1] = maxPrice(num-1);
        }
        for (int i=1;i<num+1;i++) {
            if (A[num] < A[num-i] + P[i]) {
                A[num] = A[num-i] + P[i];
            }
        }
        return A[num];
    }

}

2. Bottom-Up

import java.util.*;

public class Main {
    static int[] A; // 해당 인덱스 개수의 카드를 구매하는 최대 금액
    static int[] P; // 인덱스 개수의 카드를 포함하는 카드팩의 가격
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cardNum = sc.nextInt();
        P = new int[cardNum+1];
        A = new int[cardNum+1];
        for (int i=1;i<cardNum+1;i++) {
            P[i] = sc.nextInt(); // 각 카드 팩의 가격 받아오기
        }
        System.out.println(maxPrice(cardNum));
    }

    static int maxPrice(int num) {
        // Bottom-Up 방식
        // A[n] = n개의 카드를 구매하는 최대 금액, P[i] = i개의 카드를 포함하는 카드팩의 가격
        // 점화식 : A[n] = max(A[n-1] + p[i])
        A[1] = 1;
        for (int i=1;i<num+1;i++) {
            for (int j=1;j<i+1;j++) {
                if (A[i] < A[i-j] + P[j]) {
                    A[i] = A[i-j] + P[j];
                }
            }
        }
        return A[num];
    }
}

문제 출처 : https://www.acmicpc.net/problem/11052

1. Top-Down

import java.util.Scanner;

public class Main {
    static int[] memo;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        memo = new int[n+1];
        memo[0] = 1;
        memo[1] = 1;
        System.out.println(tiling(n));
    }

    public static int tiling(int num) {
        // Top-Down 방식
        // A[n] = 2*n 직사각형을 타일로 채우는 방법의 수
        // 점화식 : A[n] = A[n-1] + A[n-2]*2 (세로로 하나 놓았을 때 + 가로로 2개 놓았을 때와 2*2타일을 1개 놓았을 때)
        if (num < 2) { // 예외처리
            return memo[num];
        }
        if (memo[num-1] == 0) { // 푼 적 없는 부분 문제의 경우
            memo[num-1] = tiling(num-1);
        }
        if (memo[num-2] == 0) { // 푼 적 없는 부분 문제의 경우
            memo[num-2] = tiling(num-2);
        }
        memo[num] = memo[num-1] + memo[num-2]*2;
        memo[num] %= 10007;
        return memo[num];
    }
}

2. Bottom-Up

import java.util.Scanner;

public class Main {
    static int[] memo;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        memo = new int[n+1];
        memo[0] = 1;
        memo[1] = 1;
        System.out.println(tiling(n));
    }

    public static int tiling(int num) {
        // Bottom-Up 방식
        // A[n] = 2*n 직사각형을 타일로 채우는 방법의 수
        // 점화식 : A[n] = A[n-1] + A[n-2]*2 (세로로 하나 놓았을 때 + 가로로 2개 놓았을 때와 2*2타일을 한개 놓았을 때)
        if (num < 2) {
            return memo[num];
        }
        for (int i=2;i<num+1;i++) {
            memo[i] = memo[i-1] + memo[i-2]*2;
            memo[i] %= 10007;
        }
        return memo[num];
    }
}

1. Top-Down 방식

import java.util.Scanner;

public class Main {
    static int[] memo;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        memo = new int[n+1];
        memo[0] = 1;
        memo[1] = 1;
        System.out.println(tiling(n));
    }

    public static int tiling(int num) {
        // Top-Down 방식
        // A[n] = 2*n 직사각형을 타일로 채우는 방법의 수
        // 점화식 : A[n] = A[n-1] + A[n-2] (세로로 하나 놓았을 때 + 가로로 2개 놓았을 때)
        if (num < 2) { // 예외처리
            return memo[num];
        }
        if (memo[num-1] == 0) { // 푼 적 없는 부분 문제의 경우
            memo[num-1] = tiling(num-1);
        }
        if (memo[num-2] == 0) { // 푼 적 없는 부분 문제의 경우
            memo[num-2] = tiling(num-2);
        }
        memo[num] = memo[num-1] + memo[num-2];
        memo[num] %= 10007;
        return memo[num];
    }
}

2. Bottom-Up 방식

import java.util.Scanner;

public class Main {
    static int[] memo;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        memo = new int[n+1];
        memo[0] = 1;
        memo[1] = 1;
        System.out.println(tiling(n));
    }

    public static int tiling(int num) {
        // Bottom-Up 방식
        // A[n] = 2*n 직사각형을 타일로 채우는 방법의 수
        // 점화식 : A[n] = A[n-1] + A[n-2] (세로로 하나 놓았을 때 + 가로로 2개 놓았을 때)
        if (num < 2) {
            return memo[num];
        }
        for (int i=2;i<num+1;i++) {
            memo[i] = memo[i-1] + memo[i-2];
            memo[i] %= 10007;
        }
        return memo[num];
    }
}

1. Top-Down 방식

import java.util.*;

public class Main{
    public static int[] memo; // memorization을 위한 배열

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        memo = new int[num+1];
        memo[0] = 0;
        memo[1] = 0;
        System.out.println(makeOne(num));
    }

    public static int makeOne(int num) {
    	// Top-Down 방식
        // D[n] : n을 1로 만들기 위해 사용되는 연산의 횟수
        // 점화식 : D[n] = min(D[n/3], D[n/2], D[n-1]) + 1
        if (num < 2) { // 예외처리
            return 0;
        }
        int temp; // 연산 최소 횟수 값을 저장할 변수
        if (memo[num-1] == 0) { // 부분 문제가 풀린 적이 없음
            memo[num-1] = makeOne(num-1);
        }
        temp = memo[num-1];
        if (num%2 == 0) { // 2로 나누어떨어지는 경우
            if(memo[num/2] == 0) { // 부분 문제가 풀린 적이 없음
                memo[num/2] = makeOne(num/2);
            }
            if (temp > memo[num/2]) { // 2로 나눈 경우가 연산 횟수가 더 적으면
                temp = memo[num/2];
            }
        }
        if (num%3 == 0) { // 3으로 나누어 떨어지는 경우
            if(memo[num/3] == 0) { // 부분 문제가 풀린 적이 없음
                memo[num/3] = makeOne(num/3);
            }
            if (temp > memo[num/3]) { // 3으로 나눈 경우가 연산 횟수가 더 적으면
                temp = memo[num/3];
            }
        }
        memo[num] = temp+1; // 얻은 연산 횟수 최소값을 저장
        return memo[num];
    }
}

2. Bottom-Up 방식

import java.util.*;

public class Main{
    public static int[] memo; // memorization을 위한 배열

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        memo = new int[num+1];
        memo[0] = 0;
        memo[1] = 0;
        System.out.println(makeOne(num));
    }

    public static int makeOne(int num) {
    	// Bottom-Up 방식
        // D[n] : n을 1로 만들기 위해 사용되는 연산의 횟수
        // 점화식 : D[n] = min(D[n/3], D[n/2], D[n-1]) + 1
        for (int i=2;i<num+1;i++) {
            memo[i] = memo[i-1] + 1; // n-1의 경우
            if (i%2 == 0) { // n/2의 경우
                if (memo[i/2] + 1 < memo[i]) {
                    memo[i] = memo[i/2] + 1;
                }
            }
            if (i%3 == 0) { // n/3의 경우
                if (memo[i/3] + 1 < memo[i]) {
                    memo[i] = memo[i/3] + 1;
                }
            }
        }
        return memo[num];
    }
}

해설은 주석 참고

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Double> operand = new Stack<>(); // 피연산자 스택
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 피연산자의 개수
        Double[] operandArray = new Double[n]; // 피연산자들을 저장하는 배열
        String cmd = sc.next(); // 수식 받아오기
        for (int i=0;i<n;i++) {
            operandArray[i] = sc.nextDouble(); // 입력받은 정수 피연산자에 할당
        }
        // 알파벳으로 입력받는 피연산자를 해당 알파벳에 할당되는 정수로 접근하기 위한 방법
        // -> ASCII 코드 사용
        // 각 알파벳은 A = 65, ..., Z = 90의 아스키 코드 값을 갖는다.
        // Character형을 int형으로 형변환 시키면 해당 아스키 코드 값을 반환한다.
        // ex) int('A') = 65
        // A는 첫번째로 입력받은 정수를 의미하므로 정수 저장 배열의 0번째 원소에 접근하면 된다.
        // 이를 수행하기 위한 방법 : operandArray[(int)입력된알파벳 - (int)'A']]
        // ex) C에 할당된 정수(배열의 인덱스 2번 원소) 접근하기
        // -> operandArray[(int)'C' - (int)'A']] 이는 곧 operandArray[2]와 같은 의미를 갖는다.

        for (int i=0;i<cmd.length();i++) {
            double operand_1, operand_2 = 0;
            switch (cmd.charAt(i)) { // 연산자가 들어올 경우 피연산자 스택의 상위 2개 항목을 연산하고 다시 push해줌
                case '+' :
                    operand_2 = operand.pop();
                    operand_1 = operand.pop();
                    operand.push(operand_1 + operand_2);
                    break;
                case '-' :
                    operand_2 = operand.pop();
                    operand_1 = operand.pop();
                    operand.push(operand_1 - operand_2);
                    break;
                case '*' :
                    operand_2 = operand.pop();
                    operand_1 = operand.pop();
                    operand.push(operand_1 * operand_2);
                    break;
                case '/' :
                    operand_2 = operand.pop();
                    operand_1 = operand.pop();
                    operand.push(operand_1 / operand_2);
                    break;
                default: // 피연산자라면
                    operand.push(operandArray[(int)cmd.charAt(i) - (int)'A']);// 피연산자의 정수값 stack에 넣어주기
                    break;
            }
        }
        System.out.printf("%.2f", operand.pop()); // 모든 연산을 처리한 후에 최종 결과는 피연산자 스택에 한개의 항목으로 남게 됨
    }
}

문제 출처 : https://www.acmicpc.net/problem/1935

2진수의 각 3자리는 8진수의 1자리로 변환된다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String binaryNum = sc.nextLine();
        // 2진수를 8진수로 변환하면 2진수의 자리수 3개가 8진수 자리수 1개로 변환된다.
        if (binaryNum.length()%3 == 1) { // 2진수 가장 앞의 한자리가 8진수의 첫자리를 의미
            System.out.print(Character.getNumericValue(binaryNum.charAt(0))*1);
        } else if (binaryNum.length()%3 == 2) { // 2진수 가장 앞의 두자리가 8진수의 첫자리를 의미
            System.out.print(Character.getNumericValue(binaryNum.charAt(0))*2 +
                    Character.getNumericValue(binaryNum.charAt(1))*1);
        }
        // 2진수의 자리수가 3의 배수임
        for (int i=binaryNum.length()%3;i<binaryNum.length();i+=3) { // 2진수의 3자리를 8진수 1자리로 변환하기 때문에 i값은 3씩 늘어남
            // 각 2진수 3자리의 2^0자리는 *1, 2^1자리는 *2, 2^2는 *4를 해주고 모두 더하여 8진수 한자리를 구한다.
            System.out.print(Character.getNumericValue(binaryNum.charAt(i))*4 +
                    Character.getNumericValue(binaryNum.charAt(i+1))*2 +
                    Character.getNumericValue(binaryNum.charAt(i+2))*1);
        }
    }
}

문제 출처 : https://www.acmicpc.net/problem/1373

수빈이가 이동하는 방법은 +D 또는 -D 밖에 없다. -> 수빈이 동생을 찾기 위해서는 수빈과 동생과의 거리가 D의 배수여야 한다.

동생이 한명이라면? -> D = 수빈과 동생과의 거리의 약수이면 된다.

동생이 n명이라면? -> D = 수빈과 동생들과의 거리들의 공약수이면 된다.

D의 최대값 = 거리들의 최대공약수

즉, 최대공약수를 구하는 알고리즘을 사용하여 해결하면 된다.

최대공약수를 구하는 알고리즘은 유클리드 호제법을 사용했다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);;
        int n = sc.nextInt(); // 동생 n명
        int s = sc.nextInt(); // 수빈의 위치 = s

        int[] distance = new int[n]; // 수빈과 동생과의 거리 모음

        // 동생 n명과 수빈과의 거리들의 최대공약수를 구하면 D의 최대값이 된다.
        for (int i=0;i<n;i++) { // 거리 입력 반복문
            int position = sc.nextInt();
            distance[i] = Math.abs(s-position); // Math.abs : 절대값 구하는 메소드
        }
        int answer = distance[0];
        for (int i=1;i<n;i++) {
            answer = gcd(answer, distance[i]);
        }
        System.out.println(answer);
    }

    public static int gcd(int a, int b) { // 유클리드 호제법을 사용한 최대공약수 구하기
        while (b != 0) {
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
}

문제 출처 : https://www.acmicpc.net/problem/17087

팩토리얼에서 0의 개수란?

ex) 10! = 362800 -> 2개

팩토리얼에서 0의 개수를 구하는 방법은 팩토리얼의 인수에 2*5(10)이 들어있는 개수를 구하면 된다.

(0을 만들 수 있는 방법이 2*5밖에 없기 떄문)

인수들에서 5를 포함하는 수보다(5의 배수) 2를 포함하는 수가 더 많기 떄문에

5를 포함하는 인수들의 개수를 구해주면 팩토리얼에 들어가는 0의 개수를 알아낼 수 있다.

이 때, 5*5 또는 5*5*5처럼 5가 여러번 들어가는 경우도 고려해주어야한다.

ex)

입력이 100이라고 가정하면,

100/5 = 20 -> 5가 20번 들어감

100/25 = 4 -> 5가 2개 들어가는 경우는 4번

따라서 20 + 4 = 24

100!에 들어있는 0의 개수는 총 24개이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int factorial = sc.nextInt();
        // 인수들 중 5의 개수가 2의 개수보다 많기 때문에 5의 개수를 세어주면 된다.
        int num_of_5 = factorial/5;
        int num_of_25 = factorial/25; // 5가 2개 들어가는 경우들 추가로 세어주어야 함
        int num_of_125 = factorial/125; // N의 범위가 500까지이므로 5개 3번 들어가는 경우(125)도 있을 수 있음
        System.out.println(num_of_5 + num_of_25 + num_of_125);
    }
}

문제 출처 : https://www.acmicpc.net/problem/1676

소수의 개수를 파악하는데 에라토스체네스의 체를 사용했다.

에라토스체네스의 체는 2개의 단계를 반복 수행하는 것으로 이루어진다.

   1. 지워지지 않은 수 중에서 가장 작은 수 -> 소수이다.

   2. 1단계에서 구한 소수의 배수들을 모두 지원준다.
        // 해당과정 반복

설명은 주석 참고

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int sNum = sc.nextInt();
        int eNum = sc.nextInt();
        int[] prime = new int[eNum-sNum+1]; // 소수 저장
        int pn = 0; // 소수의 개수
        boolean[] check = new boolean[eNum+1]; // 에라토스체네스의 체 구현 (지워지면 true)
        // 소수의 개수를 파악하는데 에라토스체네스의 체를 사용
        // 에라토스체네스의 체는 2개의 단계를 반복 수행하는 것으로 이루어진다.
        // 1. 지워지지 않은 수 중에서 가장 작은 수 -> 소수이다.
        // 2. 1단계에서 구한 소수의 배수들을 모두 지원준다.
        // 해당과정 반복
        for (int i=2;i<eNum+1;i++) { // 들어온 정수들과 그 사이 정수들에 대해 소수 판별
            // 그 사이 정수들에 대한 것이라 하더라도 i=2부터 수행해주어야 소수들이 제대로 지워짐
            if (check[i] ==  false) { // 해당 수가 지워져 있는지 확인 (1단계)
                // 지워져 있지 않다면(false) 소수임
                if (i >= sNum) { // 시작 범위 보다 큰 정수만
                    prime[pn++] = i; // 구한 소수 배열에 넣어주고, 개수 갱신
                }
                for (int j=i+i;j<=eNum;j+=i) { // 구한 소수의 배수들을 모두 지워줌 (2단계)
                    // j 값은 i*2, ..., i(i+1), i(i+2), ...순으로 증가한다.
                    // j=i*i로 사용하면 시간을 더 단축할 수 있지만 
                    // 해당 문제의 입력의 범위에서 i는 최대 1,000,000까지 들어올 수 있다.
                    // 이 때 i*i는 java에서 int의 범위인 -2147483648 ~ 2147483647를 넘어가기 때문에 런타임에러가 발생하게 된다.
                    // 때문에 입력이 큰 수에 대해서는 j의 시작 값을 i+i 또는 i*2로 설정해주어야 한다.
                    
                    // j=i*i의 경우에 j 값이 i*2, ... 부터 시작하지 않는 이유는
                    // 예를 들어 i=6이라면 6보다 작은 수에 대한 배수들은 이미 지워졌기 때문이다. (i=2~5일 때 이미 각 배수들이 모두 지워졌으므로 이 과정을 스킵할 수 있음)
                    check[j] = true; // 해당 수 지우기
                }
            }
        }
        for (int i=0;i<pn;i++) {
            System.out.println(prime[i]);
        }
    }
}

문제 출처 : https://www.acmicpc.net/problem/1929

소수를 판별하기 위해서는 그 수가 소인수(자연수를 나누어 떨어뜨리는 약수 중 소수인 수)를 갖는 지 확인해야한다.

어떤 수가 소수가 아니라면, 그 수(N)는 N = a*b (a, b는 소수)꼴로 나타낼 수 있다.

이 때, a>b 라고 하면, a는 언제나 루트(N)보다 작은 값을 가지고, b는 루트(N)보다 큰 값을 가진다.

그러므로 루트(N)보다 작은 수에 대해서만 N이 나누어떨어지는지 확인하면 N이 소수인지의 여부를 파악할 수 있다.

반복문은 루트(N)번 반복되며 시간 복잡도는 O(루트(N))이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        int num_of_prime = 0;
        for (int i=0;i<cnt;i++) {
            int num = sc.nextInt();
            if (checkPrime(num)) { // 소수 맞으면 조건문 들어감
                num_of_prime++; // 소수 개수 1개 추가
            }
        }
        System.out.println(num_of_prime);
    }

    public static boolean checkPrime(int num) {
        if (num < 2) { // 2보다 작은 소수는 없다.
            return false;
        }
        // i는 num이 소수인지 판별하기 위해 나누어주는 수(2부터 나누어주면 됨)
        for (int i=2;i*i<=num;i++) { //java에서 int의 범위는 -2147483648 ~ 2147483647 (num의 최대 입력인 1000을 충분히 수용가능)
            if (num%i == 0) { // 나누어 떨어지는 수가 존재한다면
                return false; // 소수가 아니다.
            }
        }
        return true; // 위 조건들을 모두 통과한다면 소수 맞음
    }
}

문제 출처 : https://www.acmicpc.net/problem/1978