17433 신비로운 수 [JAVA]

문제 설명은 https://www.acmicpc.net/problem/17433

에서 직접 확인하자..!

 

 

처음 시도 방법

n개의 수가 같은 나머지를 가지게 하는 값 M을 찾아야 한다.

만약 a와 b가 다른 수 이면, 특정 수 부터는 a와 b를 나눈 나머지가 항상 다를 수 밖에 없다.

 

그렇기에 이러한 limit 지점을 찾고, 2부터 가능한 M 중 최댓값을 반환하면 되지 않을까 ?

라는 생각으로 출발했다.

 

주어진 수 배열을 Set에 넣어 중복없이 만들고 다시 List에 넣고 정렬하여 사용했다.

(중복된 수 끼리는 항상 나머지가 같으니깐)

 

정렬 후 1,2번째 원소를 기준으로 limit을 설정했다.

1번째 원소를 a 2번째 원소를 b라 가정하면

가능한 경우의 수는

 

a<0, b>0

a<0, b<0

a>0, b>0

 

위 3가지 밖에 존재하지 않고

 

각 경우의 수에서 limit은

 

1-> a의 절댓값 + b

2-> a의 절댓값

3-> b

이다.

 

이를 바탕으로 구현한 코드는 아래와 같다.

import java.util.*;

public class Main {


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        long st = System.currentTimeMillis();
        for (int i = 0; i < t; i++) {
//            int n = sc.nextInt();
            int n = 2000;
            Set<Integer> numSet = new HashSet<>();

            for (int j = 0; j < n; j++) {
//                int num =sc.nextInt();
                int num = (int)(Math.random()*10000);
                numSet.add(num);
            }
            if(numSet.size() == 1){
                System.out.println("INFINITY");
                continue;
            }

            List<Integer> numList = new ArrayList<>(numSet);
            Collections.sort(numList);

            int ans = 1;

            Integer first = numList.get(0);
            Integer second = numList.get(1);
            int limit = 0;
            if(second<0){
                //case 2
                limit = Math.abs(first);
            }else if(first<0){
                //case 1
                limit = Math.abs(first) + second;
            }else{
                limit = second;
            }

            for (int q = 2; q <= limit; q++) {
                int firstRemainder = getRemainder(first,q);

                int skipCount = 1;
                boolean madeFlag = true;
                for (Integer p : numList) {
                    //skip first
                    if(skipCount-- > 0)
                        continue;
                    int remainder = getRemainder(p, q);
                    if(firstRemainder != remainder){
                        madeFlag =false;
                        break;
                    }
                }

                if(madeFlag)
                    ans = q;
            }

            System.out.println(ans);
        }
        long ed = System.currentTimeMillis();
        System.out.println(ed-st);
    }

    static int getRemainder(int p, int q){
        int a = Math.floorDiv(p,q);
        return p-a*q;
    }

}

(시간 테스트 해보려고 난수를 좀 넣었다)

시간 초과가 발생했다.

 

그래서 확인해보니 문제 limit이 0.25초로 좀 빡빡하게 잡혀있어 뭔가 수학적으로 푸는건가 싶어 찾아보니

 

https://youseop.github.io/2020-11-30-BAEKJOON-17433_%EC%8B%A0%EB%B9%84%EB%A1%9C%EC%9A%B4%EC%88%98/

BAEKJOON#17433 신비로운 수

 

 

 

a,b가 m에 대해 같은 나머지를 가진다면 두 수의 차 b-a는 m의 배수가 된다 (나머지가 0이 되니)

.... 이걸 이용하면 결국 각 배열 원소의 차이의 최대 공약수를 (유클리드 호제법을 이용해서) 구하면 문제의 정답을 찾을 수 있게 된다..

 

즉, A1,A2의 최대공약수를 G1이라했을 때

G1과 A3의 최대 공약수 G2

G2와 A4의 최대 공약수 G3 

...

이런식으로 나아가서 전체 배열 차의 최대 공약수를 구해주면 된다.

 

import java.util.*;

public class Main {


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            Set<Integer> numSet = new HashSet<>();

            for (int j = 0; j < n; j++) {
                int num =sc.nextInt();
                numSet.add(num);
            }
            if(numSet.size() == 1){
                System.out.println("INFINITY");
                continue;
            }

            List<Integer> numList = new ArrayList<>(numSet);
            Collections.sort(numList);
            Integer[] arr = numList.toArray(new Integer[0]);

            int ans = arr[1] - arr[0];

            for (int j = 1; j < arr.length-1; j++) {
                int now = arr[j+1] - arr[j];
                ans = gcd(now, ans);
            }
            if(ans == 0)
                System.out.println("INFINITY");
            else
                System.out.println(ans);
        }

    }

    static int gcd(int a, int b) { // a > b 일때
        if(b == 0) return a;	// gcd를 찾았다면 그 몫을 return
        else return gcd(b, a % b);
    }

}