21.07.30 기록

• 백준 알고리즘 9020 풀이

  • 나의 풀이(메모리 15.8MB, 시간 168ms로 통과)
    

    (1)에라토스테네스의 체를 사용하여 boolean 배열에서 소수 인덱스 값에 false를 준다.
    

    (2)N의 중앙값(N/2)을 기준으로 최소 2까지 루프를 돌며 소수의 합을 찾는다.
    

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class B9020 {
      public static boolean[] prime = new boolean[10001]; //N의 최대 범위는 10,000이다.
  
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringBuilder sb = new StringBuilder();
          int testCase = Integer.parseInt(br.readLine());
  
          getPrime();
          for(int i = 0; i < testCase; i++) {
              int N = Integer.parseInt(br.readLine());
  
              for(int j = N/2; j >= 2; j--) { //(N/2)부터 2까지 루프 반복
                  if(!prime[j]) { //j값이 소수일 때
                      if(!prime[N-j]) { //N-j값도 소수이면
                          sb.append(j + " " + (N-j)).append("\n");  //StringBuilder에 저장한다.
                          break; //루프 벗어나기
                      }
                  }
              }
          }
          System.out.println(sb);
      }
  
      public static void getPrime() {
          prime[0] = prime[1] = true;
  
          for(int i = 2; i <= Math.sqrt(prime.length); i++) {
              if(prime[i]) { continue; }
              for(int j = (i*i); j < prime.length ; j+=i) {
                  prime[j] = true;
              }
          }
      }
  }
  

  
  

  • 해설 (메모리 15.2MB, 시간 164ms로 통과)
    

    내 풀이는 하나의 파티션 값에만 N/2를 적용했다면, 해설은 두 파티션 값에 모두 N/2를 적용하여 풀이했다.
    

   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
  
   public  class B9020 {
       public static boolean[] prime = new boolean[10001];
  
       public static void main(String[] args) throws IOException {
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           StringBuilder sb = new StringBuilder();
           int testCase = Integer.parseInt(br.readLine());
  
           getPrime();
           while(testCase-- > 0) {
               int N = Integer.parseInt(br.readLine());
               int firstPartition = N / 2;
               int secondPartition = N / 2;
  
               while(true) {
                   if(!prime[firstPartition] && !prime[secondPartition]) {
                       sb.append(firstPartition).append(" ").append(secondPartition).append("\n");
                       break;
                   }
  
                   firstPartition--;
                   secondPartition++;
               }
           }
           System.out.println(sb);
       }
  
       public static void getPrime() {
           prime[0] = prime[1] = true;
  
           for(int i = 2; i <= Math.sqrt(prime.length); i++) {
               if(prime[i]) { continue; }
               for(int j = (i*i); j < prime.length; j+=i) {
                   prime[j] = true;
               }
           }
  
       }
   }