[BaekJoon/백준] 2981번

검문 문제 ( 검문이랑 1도상관없지만 )

 

N개의 수를 M으로 나누었을 때, 나머지가 전부 같은 M을 찾는 문제.

굉~장히 어려웠다. 개인적으로 너무 어려웠다. 이틀정도 못풀었다.

 

수학적인 사고가 요구된다. 그 접근만 알게 되면 쉽게 느끼질 수도 있다.

#include <stdio.h>
#include <stdlib.h>

int N;
int a[100];
int gc[100];
int p;

int compar(int *a, int *b) {
    if(*a < *b)
        return -1;
    else if(*a > *b)
        return 1;
    else
        return 0;
}
int gcd(int a, int b) {
    int temp;
    while(b != 0) {
        temp = a;
        a = b;
        b = temp % b;
    }
    return a;
}

void print_result(int a) {
    
    for(int i = 2; i * i <= a; i++) {
        if(a % i == 0) {
            gc[p++] = i;
            if(i != a / i) gc[p++] = a / i;
        }
    }
    gc[p++] = a; // 마지막에 자기자신도 추가. ( 1부터 시작하지 않았기에 자기자신에 대응되는 값이 추가되지 않아서 직접 추가)
    
    qsort(gc, p, sizeof(int), compar);
    
    for(int i = 0; i < p; i++) {
        printf("%d ", gc[i]);
    }
}

int main() {
    int i;
    int G; // 최대공약수 연산에 쓰일 변수
    
    scanf("%d", &N);
    
    for(i = 0; i < N; i++)
        scanf("%d", &a[i]);
    
    G = abs(a[1] - a[0]);
    
    // 각 값들의 공통되는 최대공약수를 구한다.
    // N = 2 일지라도, abs(a[1] - a[0]) 만으로 해결된다 ( 공통이 필요없으니, 1 * M 을 생각하여 M이 최대로 만들어짐 )
    for(int i = 2; i < N; i++)
        G = gcd(G, abs(a[i] - a[i - 1]));
    
    print_result(G);
}
/*
 
 v[1] - v[0] = (share[1] - share[0]) * M
 v[2] - v[1] = (share[2] - share[1]) * M
 v[3] - v[2] = (share[3] - share[2]) * M
 
 (share[i] - share[i - 1])은 알 수 없다.
 하지만 어쟀든 v[i] - v[i - 1]은 두 수의 곱으로 이루어져 있고
 이들 중 곱하는 수가 최대로 중복되는 수인 M의 경우를 찾아내면 된다.
 
 */

 

문제 풀이는 아래 두 블로그의 풀이가 짱이다.

cocoon1787.tistory.com/214

hooongs.tistory.com/77