문제 풀이/알고리즘

[백준] (2981) 검문

얌얌념념 2022. 12. 27. 19:50

링크 : https://www.acmicpc.net/problem/2981

사용 언어 : JAVA

내 생각

대체 왜 그랬는지는 모르겠는데 골드 4라 쉽겠지 생각했다. 근데 아무리 생각해도 어떻게 해야하는지 감도 안오고,, 혹시나 제출해봐도 계속 틀리고 시간초과나고ㅋㅋㅋ 결국 멘탈 터져서 나중에는 출력에 println 써서 0퍼 컷 당하고 그랬다ㅎㅎ;; 처음에 쉽다고 얕봐서 더 멘탈이 나간 듯 하다.

붉은 비...

결국 패배를 인정하고 구글링했다. 그리고 내 기초 지식이 부실했음을 깨닫고 컴공의 기본 of 기본인 유클리드 호제에 대해 다시 공부하였고, 까먹지 않기 위해 울면서 포스팅을 쓴다 ㅠㅠ

초기 생각

사실 맨 처음에도 유클리드 호제 같긴 했는데 당최 어떻게 써먹어야하는질 몰라서 그냥 냅다 풀었다.

for (extra = 1~MIN) {
	gcd = (i=0~N)(arr[i] - extra)들의 최대공약수
	pq.add(gcd 약수)
}

딱봐도 시간 초과나게 생김

최종

유클리드 호제법에 대한 포스팅은 여기에 따로 적어두었다.

일단 이 문제는 주어진 숫자들의 나머지를 같게 만드는 나누는 수 M을 찾는 것이 목적이다. M은 반드시 하나 이상 존재한다고 문제에 나와 있으니, 주어진 수 A, B, C, D, ... 를 다음과 같이 표현할 수 있다.

A = a*M + r,    B = b*M + r,    C = c*M + r,    D = d*M + r,  ... (M과 r은 모두 같고 M의 계수만 달라진다)

나는 처음에 여기서 r이 1~MIN(A~...)일 경우를 다 따로 생각을 해버렸기 때문에 시간 초과가 났었다. 그런데 M을 최대 공약수로 두어 찾고, 그의 약수들을 따로 카운트한다면 r이 얼마이든 상관 없어진다. 더 자세히 적어보겠다.

위에서 잠깐 언급한 것처럼 주어진 수(A, B, C, D)를 우리가 구하고자 하는 공약수 M과 특정 나머지 값 r을 사용해 수식화한 모습이다.

여기서 M을 따로 빼내기 위해 이웃한 수식의 양변을 서로 빼보자.

결과는 이렇게 된다. 이웃한 A=()와 B=()을 빼고, B=()와 C=(), C=()와 D=()를 빼었다. 그러면 공통된 나머지 r은 그 수가 무엇이었던 간에 삭제가 되고, 주어진 수와 M만이 남게 된다. 이것이 r의 경우를 일일이 생각했던게 패착이 되었던 이유다. 생각할 필요가 없다.

그럼 여기에서 보기 쉽게 A-B, B-C, C-D를 각각 X, Y, Z로 치환해보자.

이제 우리가 찾고자 하는 나누는 수 M을 어떻게 구할 수 있을지 실마리가 보인다. 바로 X, Y, Z의 최대공약수를 구하는 것이다.

N가지 수의 최대공약수(gcd)를 구하기 위해서는 총 N-1번 gcd 구하기 과정을 거치면 된다. 먼저, 맨 앞 두 수의 gcd를 구한 뒤, 그 gcd와 다음 세번째 수의 gcd를, 다시 그 gcd와 마지막 수의 gcd까지 반복하면 된다.

그렇게 구한 gcd의 약수를 출력하면 된다. 단, M은 1보다 큰 수이니 1을 포함하지 않는 데 주의한다.

// 1. 주어진 수를 정렬
arr[i=0~N-1] = br.read();
Arrays.sort(arr)

// 2. 이웃한 수끼리 뺄셈한 결과끼리 gcd를 구함
gcd = arr[i]-arr[i-1]
for(i=1~N-1){
	gcd = GCD(gcd, arr[i]-arr[i-1])
}

// 3. 구한 gcd(==M)의 약수 출력 (단, 1은 제외)
for(i=2~gcd){
	if(i가 gcd 약수면)
    	sout(i)
}

 

최종 코드

더보기 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] nums = new int[N];

        for(int i=0; i<N; i++)
            nums[i] = Integer.parseInt(br.readLine());

        // 정렬
        Arrays.sort(nums);

        // 이웃한 수의 차이끼리의 최대공약수(GCD)를 구한다
        int gcd = nums[1]-nums[0];
        for (int i = 2; i < N; i++) {
            gcd = GCD(gcd, nums[i]-nums[i-1]);
        }

        StringBuilder sb = new StringBuilder();
        PriorityQueue pq = new PriorityQueue();

        // 구한 GCD의 약수를 pq에 넣는다
        for(int i=2; i<=Math.sqrt(gcd); i++){
            // 제곱근은 따로 넣음
            if(i*i == gcd)
                pq.add(i);
            else if(gcd%i == 0) {
                pq.add(i);
                pq.add(gcd / i);
            }
        }
        // GCD도 넣음
        pq.add(gcd);

        while (!pq.isEmpty())
            sb.append(pq.poll()).append(' ');

        System.out.println(sb);
    }

    // a: 나뉠 수(B), b: 나눌 수(A%B)
    static int GCD(int a, int b){
        int tmp;
        while(b!=0){
            tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }
}

느낀점

  • 기초의 중요성
  • 사실 기업 코테에는 잘 안나오지 않을 것 같다..
저작자표시