[C/C++] 백준 #2981 검문(유클리드 호제법)

백준 온라인 저지 문제 2981번 "검문"을 해결하기 위해서는 주어진 수들로부터 차이들의 최대공약수를 구하고, 그 공약수의 약수들을 찾아 출력하는 것입니다. 

 

Solving for the Greatest Common Divisor: A Focused Approach on Paper

 

최대공약수를 찾을 때에는 유클리드 호제법을 이용하면 됩니다.

 

문제의 링크는 다음과 같습니다.

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

 

### 주요 함수 및 흐름 설명

#### 1. **`gcd(int a, int b)` 함수:**
   - 두 수의 **최대공약수(GCD, Greatest Common Divisor)**를 구하는 함수입니다.
   - 유클리드 호제법(Euclidean Algorithm)을 사용하여 `a`와 `b`의 GCD를 구합니다.
   - **유클리드 호제법**은 다음의 과정을 반복하는 알고리즘입니다:
     1. `a % b`가 0이 될 때까지, `a`를 `b`로 나누고 나머지를 `b`에 저장합니다.
     2. 최종적으로 남는 `a`가 GCD입니다.

#### 2. **`main()` 함수의 구조:**
   1. **입력받기:**
      - 첫 번째 입력은 `n`으로, 주어지는 수의 개수입니다.
      - 두 번째 입력은 `n`개의 수를 배열 `v`에 저장합니다.
   
   2. **최소값 찾기:**
      - 배열에서 가장 작은 값을 찾고, 이를 `min`에 저장합니다.
      - 이 값은 모든 수들에서 빼는 기준점이 됩니다.
   
   3. **모든 차이들의 최대공약수 구하기:**
      - 배열의 각 요소에서 `min`을 뺀 값들을 비교해 **GCD**를 구합니다.
      - 첫 번째 차이를 기준으로 하여 GCD를 업데이트합니다.

   4. **GCD의 약수 찾기:**
      - GCD의 약수를 찾는 루프가 두 번 있습니다.
      - 첫 번째 루프에서는 `2`부터 `sqrt(GCD)`까지의 약수를 찾습니다.
      - 두 번째 루프에서는 그와 대칭되는 나눗셈 결과 값을 찾습니다.

   5. **출력:**
      - `GCD`의 모든 약수를 오름차순으로 출력합니다.

### 코드 분석

int n, v[100], min, g = 0, s;

- `n`: 입력받는 수의 개수.
- `v[100]`: 입력받은 수들을 저장하는 배열 (최대 100개).
- `min`: 주어진 수들 중에서 가장 작은 값.
- `g`: 차이들의 GCD.
- `s`: 약수를 찾기 위한 변수.

 

 

scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", v + i);

- 첫 번째 입력으로 `n`을 받고, 그 다음 `n`개의 숫자를 배열 `v`에 저장합니다.

 

 

min = v[0];
for(int i = 1; i < n; i++) min = min > v[i] ? v[i] : min;

- 배열에서 가장 작은 수를 찾아 `min`에 저장합니다.

 

 

for(int i = 0; i < n; i++)
{
    if(v[i] == min) continue;
    g = (g == 0) ? v[i] - min : gcd(v[i] - min, g);
}

- 배열의 각 수에서 `min`을 뺀 차이의 GCD를 구합니다.
- 첫 번째 차이를 기준으로, 이후 차이들에 대해 GCD를 점진적으로 구합니다.

 

 

for(s = 2; s*s <= g; s++)
    if(g%s == 0) printf("%d ", s);

- `2`부터 `sqrt(g)`까지 반복하면서 `g`의 약수를 출력합니다.

 

 

s--;
if(s*s == g) s--;
for(; s >= 1; s--)
    if(g%s == 0) printf("%d ", g/s);

- 대칭되는 나눗셈 결과 약수도 출력하여 약수를 오름차순으로 출력하는 구조입니다.

### 프로그램의 목적
주어진 여러 수에서 공통적으로 나눌 수 있는 **M**을 찾는 문제입니다. M은 이 수들의 차이들의 공통된 약수입니다. 예를 들어, 입력이 `[6, 34, 38]`이라면, 차이는 `[34 - 6, 38 - 6] = [28, 32]`이고, 이 차이들의 최대공약수는 `4`입니다. 따라서 답은 `4`의 약수인 `2`와 `4`가 됩니다.

 

위의 소스를 정리하여 만든 제 소스입니다.

//----------------------------------------------------------
//    baekjoon #2981
//        - by Aubrey Choi
//        - created at 2019-06-17
//----------------------------------------------------------
#include <stdio.h>

int gcd(int a, int b)
{
    while(b) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int main()
{
    int n, v[100], min, g = 0, s;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", v + i);
    min = v[0];
    for(int i = 1; i < n; i++) min = min > v[i] ? v[i] : min;
    for(int i = 0; i < n; i++)
    {
        if(v[i] == min) continue;
        g = (g == 0) ? v[i] - min : gcd(v[i] - min, g);
    }
    for(s = 2; s*s <= g; s++)
        if(g%s == 0) printf("%d ", s);
    s--;
    if(s*s == g) s--;
    for(; s >= 1; s--)
        if(g%s == 0) printf("%d ", g/s);
    return 0;
}