[BaekJoon/백준] 9020번

해당 문제는 이전 1929번의 알고리즘인 '에라토스테네스의 체' 를 활용하여 풀었다.

 

코드부터 보고 설명..

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for(int x=0; x<T; x++) {
            int a = scanner.nextInt();

            int arr[] = new int[a + 1];

            for (int i = 2; i <= a; i++) {
                arr[i] = i;
            }

            for (int i = 2; i*i <= a; i++) {
                for (int j = i + i; j <= a; j += i) {
                    if (arr[j] == 0) continue;
                    arr[j] = 0;
                }
            }

            int key=a;
            String call="";

            //이중포문을 짤때 배열을 앞에서 a/2까지 돌면서, a에서 뺀 값 arr[값]이 0이 아니면 됌. 그리고 대소비교.
            for(int i=2; i<=a/2; i++) {
                if(arr[i]==0) continue;
                if(arr[a-arr[i]]!=0) {
                    if(key>arr[a - arr[i]] - arr[i]) {
                        key = (a-arr[i]) - arr[i];
                        call = "" +arr[i]+ " " + (a-arr[i]);
                    }
                }
            }
            System.out.println(call);
        }
    }
}

 

주석처리된 부분에 대해서 더 설명해보겠습니다.

문제에서 2 초과의 짝수는 모두 소수들의 합으로 표현할 수 있다고 했습니다. 그래서 일단 주어진 수 이하의 모든 소수를 '에라토스테네스의 체' 알고리즘으로 구분해놨습니다. arr[index] = index 를 통해 각 배열 안에 인덱스에 맞는 숫자를 넣어준 뒤, arr[index] 에서 index가 소수가 아니라면 0을 넣어줬습니다. 이렇게 해서 배열에서 0이 아닌 값들은 모두 소수로 도출시킨 상태입니다.

 

소수 + 소수가 주어진 수가 된다는 문제의 말에 따라, 배열에서 처음부터 a/2까지 (ex, a=12일때 5+7 = 7+5 이므로 순서가 바뀌는 중복은 피해주기 위한 목적) 돌아주게 합니다. 그러면 여기의 i는 무조건 앞으로 더해지는 수 보다 작거나 같은 수가 됩니다. 반을 넘지 않았기 때문이죠.

 

그렇게 처음 포문을 돌다가 arr[i]가 0이 아닌 값을 찾았을 때, 즉 배열에서 가장 작은 소수를 찾았을 때 a 에서 이 수를 빼줍니다. 그리고 그 수를 인덱스로 갖는 arr의 값이 0이 아닌지 확인합니다. 소수1 + 소수2 = 값 이랬으니까 소수1을 픽했으면 소수2는 값 - 소수1일 테니까요.

이 값이 배열에 0이 아닌 상태로 존재하는지(=소수인지) 확인한 뒤 소수이면 저장해놓습니다. 그리고 배열을 계속 돌면서 이런 값이 한번 더 나올 경우 두 수의 차가 작은 것으로 다시 업데이트하며 포문을 돌리는 과정입니다.

 

key가 최소값을 찾는데 쓰이는 용도이구 초기화는 a값으로 해줬습니다. 차가 a보다 클 리는 없으므로 처음 찾은 두 소수는 그대로 저장되겠고 또 다른 두 소수가 있다면 차를 이 값과 비교해준뒤 더 작을 경우에만 업데이트해주고, 다른 두 소수가 없으면 이 값 그대로 가겠죠.

 

그리고 call을 출력해줍니다. 끗.