[BOJ] 백준 18821번 : 홀수와 짝수의 대결 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/18821

18821번: 홀수와 짝수의 대결

문제

일반적인 정의와 달리 이 문제에서는 홀수와 짝수를 다음과 같이 정의한다.

1 이상의 자연수 k는 소수의 곱으로 표현할 수 있고, 그 표현 방법은 소수의 순서를 바꾸는 경우를 제외하면 유일하다. 이때 사용된 소수의 개수가 2의 배수가 아니면 k는 짝수, 아니면 k는 홀수이다. (k = 1일 때는 소수 0개의 곱이고, 0은 2의 배수이다.) 같은 소수가 여러 번 사용되었을 경우, 사용될 때마다 하나씩 세어야 한다.

풀이

처음에는 1일 때만 E이고, 나머지는 O가 나오는 것 같아서 그대로 제출해 보았더니, 섭테2만 통과하였습니다. 이게 도대체 뭘까하고 구글링을 하다보니 폴리아 추측이라는 이론을 알게 되었습니다.

이것에 대한 이론은 https://en.wikipedia.org/wiki/P%C3%B3lya_conjecture 에서 참고하실 수 있고, 간단히 설명드리자면, 위 문제에서 E와 O를 만족하는 조건은 9억 이하까지만 해당이 되고, 그 이후로는 반례가 존재합니다.

따라서 1부터 10억까지 브루트포스를 돌리시면서 반례가 생기는 구간을 출력한 다음, 그 값을 따로 배열에 저장하여 예외 처리를 하면 됩니다.

소스 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    static int[][] a = { { 906150257, 906150258 }, { 906150259, 906150293 }, { 906150295, 906150307 },
            { 906150311, 906150313 }, { 906150315, 906151515 }, { 906151517, 906151575 }, { 906154583, 906154585 },
            { 906154605, 906154605 }, { 906154609, 906154757 }, { 906154763, 906154763 }, { 906154769, 906154769 },
            { 906154789, 906154789 }, { 906154791, 906154791 }, { 906154793, 906154793 }, { 906154825, 906154825 },
            { 906154829, 906154829 }, { 906154837, 906154837 }, { 906154857, 906154857 }, { 906154865, 906154881 },
            { 906154885, 906154885 }, { 906154887, 906154887 }, { 906154889, 906154889 }, { 906154891, 906154891 },
            { 906154893, 906154893 }, { 906154895, 906154907 }, { 906154909, 906154911 }, { 906154915, 906154927 },
            { 906154947, 906154949 }, { 906180359, 906180361 }, { 906180363, 906180363 }, { 906180365, 906180365 },
            { 906180367, 906180369 }, { 906180371, 906180373 }, { 906180375, 906180375 }, { 906180391, 906180517 },
            { 906180519, 906180519 }, { 906180525, 906180533 }, { 906180537, 906180553 }, { 906180555, 906192697 },
            { 906192847, 906192865 }, { 906192867, 906192903 }, { 906192905, 906192905 }, { 906192907, 906192965 },
            { 906192971, 906192971 }, { 906192979, 906192983 }, { 906192985, 906193227 }, { 906193229, 906193233 },
            { 906193245, 906193245 }, { 906193247, 906193247 }, { 906193303, 906193303 }, { 906193419, 906193419 },
            { 906193465, 906193465 }, { 906193475, 906193475 }, { 906193477, 906193477 }, { 906194931, 906194931 },
            { 906194933, 906194945 }, { 906194949, 906194949 }, { 906194951, 906194967 }, { 906194979, 906194979 },
            { 906195099, 906195099 }, { 906195109, 906195149 }, { 906195151, 906195151 }, { 906195297, 906195297 },
            { 906195299, 906195985 }, { 906195989, 906195989 }, { 906196009, 906196009 }, { 906196011, 906196013 },
            { 906196015, 906196015 }, { 906196045, 906196051 }, { 906196053, 906196055 }, { 906196057, 906196071 },
            { 906196077, 906196079 }, { 906196081, 906196081 }, { 906196083, 906196091 }, { 906196099, 906208711 },
            { 906208713, 906208713 }, { 906208731, 906208731 }, { 906209041, 906209063 }, { 906209067, 906209067 },
            { 906209069, 906209069 }, { 906209071, 906209223 }, { 906209227, 906209227 }, { 906209233, 906209235 },
            { 906209237, 906209237 }, { 906209241, 906209241 }, { 906209243, 906209271 }, { 906209283, 906209283 },
            { 906209285, 906477701 }, { 906477735, 906477811 }, { 906477867, 906477867 }, { 906477869, 906477869 },
            { 906477871, 906477899 }, { 906477901, 906477901 }, { 906477903, 906477905 }, { 906477929, 906477931 },
            { 906477933, 906477933 }, { 906477935, 906477935 }, { 906477937, 906486639 }, { 906486805, 906486805 },
            { 906486807, 906486807 }, { 906486817, 906486817 }, { 906486819, 906486819 }, { 906486821, 906486831 },
            { 906486843, 906486853 }, { 906486855, 906486855 }, { 906486909, 906486913 }, { 906486917, 906486973 },
            { 906486975, 906487001 }, { 906487005, 906487063 }, { 906487065, 906487065 }, { 906487069, 906487069 },
            { 906487071, 906487071 }, { 906487073, 906487077 }, { 906487085, 906487085 }, { 906487087, 906487101 },
            { 906487185, 906487185 }, { 906487187, 906487189 }, { 906487191, 906487191 }, { 906487193, 906487193 },
            { 906487195, 906487203 }, { 906487205, 906487205 }, { 906487259, 906487259 }, { 906487261, 906487261 },
            { 906487263, 906487263 }, { 906487271, 906487287 }, { 906487933, 906487933 }, { 906487937, 906487937 },
            { 906487949, 906487973 }, { 906487975, 906487993 }, { 906487995, 906488001 }, { 906488003, 906488003 },
            { 906488007, 906488007 }, { 906488009, 906488009 }, { 906488023, 906488025 }, { 906488027, 906488065 },
            { 906488067, 906488067 }, { 906488077, 906488079 } };
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            boolean polya = false;
            for (int i = 0; i < 137; i++) {
                if (a[i][0] <= n && n <= a[i][1]) {
                    polya = true;
                    break;
                }
            }
 
            if (n == 1 || polya) {
                bw.write("E\n");
            } else {
                bw.write("O\n");
            }
        }
        
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.