📙[Algo] 24.01.16 알고리즘

알고리즘 문제) BOJ 15711. 환상의 짝꿍  

15711번: 환상의 짝꿍

문제 요약

• 끈을 이어붙이고 소수인 끈으로 정확히 나눌 수 있다면 환상의 짝꿍
• 환상의 짝꿍인지 판단하기

시간 제한

• 1초

입력

• 테스트 케이스 T(1≤T≤500)
• 끈의 길이 A, B (1≤A,B≤2조..)

출력

• YES 또는 NO 출력

접근법

• 골드바흐의 추측 : 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.
• 3 4 ⇒ 7 : 1 6 / 2 5 / 3 4
• 3 5 ⇒ 8 : 1 7 / 2 6 / 3 5 / 4 4
• 약수 구하기 : $\sqrt{1000000000000000}$ = 1,000,000 = 1백만 연산
• 합쳐서 짝수일 경우 ⇒ 무조건 가능
• 홀수일 경우 ⇒ 계산해야
  • 9 : 2 7
  • 19 : 18 + 1
• 최악의 경우 500개 케이스에서 모두 합이 홀수가 나올 경우
  • 500 * 1백만 = 5억..?(약수구하기 할 경우 시간 초과)
  2 3 5 7 11 13 17 19 23 29 31 …
• 2의 배수, 즉 짝수인 경우 소수가 2 하나 밖에 없다.
  • 소수들 중 나머지는 다 홀수로 구성되어 있음
  • 홀 + 홀 = 짝 ⇒ 골드바흐에의해 무조건 소수의 합으로 가능
  • 짝 + 짝 = 짝 ⇒ 이 경우는 2,2밖에 없음
  • 짝 + 홀 = 홀
    • 합한 숫자에서 2를 뺐을 때 소수인가 판별해야함
      • 2부터 루트값만큼 탐색해서 나누어떨어지는게 1개이상이라면 소수 아님,, ⇒ 100만 연산,,,,
        • 조금이라도 줄이기 위해 중간에 break 걸기..? ⇒ 그래도 시초뜸, 메모이제이션도..
    • 에라토스테네스 체를 제곱근까지만 탐색
      • 소수인 애들은 따로 리스트에 담기
      • 2000000이하인 친구들은 에라토스테네스 체 배열 isPrime에서 확인
      • 그 이상인 경우
        • 모든 수는 소수를 약수로 가짐… + 왼쪽에 올 수 있는 수들 중 가장 큰 것은 $\sqrt{n}$ 이다.
        • 즉, 미리 리스트에 담은 친구들로 나누어떨어지는 지 체크
    • 1,2,3일 때 주의.. 조건 체크할 것

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 에라토스테네스 체 초기화
        boolean[] isPrime = new boolean[2000010];
        Arrays.fill(isPrime, true);

        isPrime[1] = false;
        for (int i = 2; i <= 2000000 ; i++) {
            if(!isPrime[i]) continue;

            if((long)i * i <= 2000000)
            {
                for (int j = i * i; j <= 2000000; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 따로 소수만 리스트에 담기
        ArrayList<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= 2000000; i++) {
            if(isPrime[i]) primes.add(i);
        }

        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        long A = 0, B = 0, sum = 0;
        boolean check = false;
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            A = Long.parseLong(st.nextToken());
            B = Long.parseLong(st.nextToken());
            sum = A + B;

            if (sum % 2 == 0) {
                if(sum == 2) sb.append("NO\n"); // 2를 간과하고 있었따 ^^
                else sb.append("YES\n");
            }else{
                sum -= 2;
                if(sum <= 1){
                    sb.append("NO\n");
                }else{
                    // 홀수일 경우 소수인지 안닌지 판단해야 함
//                    for (long i = 2; i * i <= sum ; i++) {
//                        if(sum % i == 0){
//                            cnt++;
//                            break;
//                        }
//                    }

                    if(sum <= 2000000){
                        if(isPrime[(int)sum]) check = true;
                        else check = false;
                    }else{
                        check = true;
                        for (int i = 0; i < primes.size(); i++) {
                            if(sum % primes.get(i) == 0){
                                check = false;
                                break;
                            }
                        }
                    }

                    if(check) sb.append("YES\n");
                    else sb.append("NO\n");
                }
            }
        }

        System.out.println(sb);
    }
}