[백준 - 24537번] 약수 계산 - Java

문제 링크

https://www.acmicpc.net/problem/24537

문제

티어: 골드 2
알고리즘: 그리디, 수학, 정수론, 유클리드 호제법

입력

출력

 $Q$줄에 걸쳐, 가지고 있는 수에서 최대공약수가 $K$가 되게끔 가능한 한 많은 수를 골랐을 때 고를 수 있는 수의 개수를 출력한다. 만약 어떻게 골라도 최대 공약수가 $K$가 되게 만들 수 없다면 대신 $-1$을 출력한다.

풀이

가지고 있는 수 중에서 일부를 골라 고른 수의 최대 공약수가 K가 되게끔 만들어야 하는데 수를 최대한 많이 골라야 한다.

N은 최대 30만이고, Q 또한 최대 30만이다. 그래서 각 K를 돌면서 N의 항목을 살펴보는 풀이는 불가능하다.

가능한 풀이는 다음과 같다.

N의 항목을 인덱스로 하는 배열에 카운트 해주고, 인덱스 1부터 1000000만까지 돌면서, 인덱스의 배수에 있는 값을 더해준다.

예를 들어 2 6 10 3 8이면, gcdCount[2]는 4가 된다.

이 과정의 시간 복잡도는 O(100만 * log100만)이다. 각 i마다 100만/i만큼 반복하기 때문이다.

그러면 gcdCount에는 인덱스가 최대 공약수가 될 수 있으면서, 수를 최대한 많이 고른 개수가 저장된다.

이제는 인덱스가 최대 공약수가 될 수 있는지를 체크해야 한다.

만약, 2의 배수의 개수가 4의 배수의 개수와 같다면 어떻게 될까? 이 경우는 4의 배수만 존재한다는 의미이므로 최대 공약수는 4가된다. 그래서 gcdCount[2]에는 -1값이 들어가야 한다.

gcdCount[2]가 -1이 되지 않으려면 100만까지 모든 2의 배수의 개수를 체크해야 한다.

그래서 4의 배수와 개수가 다르고, 6의 배수와 개수가 다르고, 8의 배수와 개수가 다르고....를 반복해서 모든 개수와 다르면 gcdCount[2]의 포함된 항목들의 최대 공약수는 2가 되는 것이다.

이를 더 쉽게 풀어서 설명하면, 4의 배수가 다르다는 것은 최대 공약수가 4가 아니라는 의미이고, 6의 배수와 개수가 다르다는 것은 최대 공약수가 6이 아니라는 의미다. 이를 100만까지 반복해서 개수가 다 다르다면 최대 공약수는 2가 되는 것이다.

이 풀이의 시간 복잡도는 O(100만 * log100만)이 된다. 개수가 다른지 같은지 체크하는 로직은 단순히 O(1)의 비교 로직이기 때문이다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      int[] gcdCount = new int[1000001];
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int i=0; i<N; i++) {
          gcdCount[Integer.parseInt(st.nextToken())] += 1;
      }
      
      for(int i=1; i<=1000000; i++) {
          for(int j=i+i; j<=1000000; j+=i) {
              gcdCount[i] += gcdCount[j];
          }
      }
      
      for(int i=1; i<=1000000; i++) {
          if(gcdCount[i] == 0) {
              gcdCount[i] = -1;
              continue;
          }
          for(int j=i+i; j<=1000000; j+=i) {
              if(gcdCount[j] > 0) {
                  if(gcdCount[i] == gcdCount[j]) {
                      //같으면 최대공약수 i를 만들 수 없음
                      gcdCount[i] = -1;
                      break;
                  }
              }
          }
      }
      StringBuilder sb = new StringBuilder();
      int Q = Integer.parseInt(br.readLine());
      for(int i=0; i<Q; i++) {
          sb.append(gcdCount[Integer.parseInt(br.readLine())]).append("\n");
      }
      System.out.println(sb.toString().trim());
  }
}