글 읽기 - 시간초과가 계속 뜨네요,,,

oehdgns 1년 전 0

시간초과에러가 뜨는데 어느부분에서 시간을 단축할 수 있을까요?

public class Baek9020 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int cnt1 = 0;
        int cnt2 = 0;
        int[] array;

        while (t-- > 0) {
            int n = sc.nextInt();
            boolean[] prime = new boolean[n + 1];
            prime[0] = prime[1] = true;

            for (int i = 2; i * i <= n; i++) {
                if (!prime[i]) {
                    for (int j = i * i; j <= n; j += i) {
                        prime[j] = true;
                    }
                }
            }

            for (int i = 1; i <= n; i++) {
                if (!prime[i]) {
                    cnt1++;
                }
            }

            array = new int[cnt1];

            for (int i = 1; i <= n; i++) {
                if (!prime[i]) {
                    array[cnt2++] = i;
                }
            }

            cnt1 = cnt2 = 0;

            for (int i = 0; i < array.length; i++) {
                int cnt4 = 0;
                for (int j = 0; j < array.length; j++) {
                    if (n == array[i] + array[j]) {
                        cnt4 = 0;
                        if (array[i] - array[j] == 0) {
                            System.out.println(array[i] + " " + array[j]);
                            cnt4 = 0;
                            cnt4++;
                            break;
                        } else if (array[i] - array[j] > 0) {
                            System.out.println(array[j] + " " + array[i]);
                            cnt4++;
                            break;
                        }
                    }
                }
                if (cnt4 == 1) {
                    break;
                }
            }
        }
    }
}

wak8835 1년 전 0

테스트케이스 t회 반복함에 있어서 소수(prime)는 한번 찾은 후에 반복 사용하셔도 무방합니다. (n <= 10,000)

wak8835 1년 전 0

추가적으로 해당 문제에서 중요히 사용할 수 있는 것은

두 소수의 차이가 가장 적은 소수 2개를 찾으라는 것입니다.

이는 n / 2 를 중심으로 하는 소수인 수 2개를 찾는 방법으로 변경하시면

O(N^2)의 탐색에서 O(N) 만큼으로 시간 복잡도를 더 줄일 수 있습니다.

+ 오타 수정

oehdgns 1년 전 1

감사합니다! 덕분에 해결했습니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과가 계속 뜨네요,,,

oehdgns 1년 전 0

wak8835 1년 전 0

wak8835 1년 전 0

oehdgns 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말