최대공약수들( BOJ 10244 )

문제 : https://www.acmicpc.net/problem/10244

10244번: 최대공약수들

 

문제 파악하기

f(lo, hi)를 A[lo] ~ A[hi] 사이의 모든 숫자의 최대공약수라고 할 때, f(lo, hi)의 값이 될 수 있는 모든 경우의 수를 구하는 문제입니다. 수열의 길이는 최대 100,000이기에 모든 구간을 확인할 수는 없지만 다행히 수열의 원소 값인 a의 범위는 1~100 사이의 정수로 범위가 작습니다. 이 점을 활용하면 문제를 해결할 수 있습니다.

 

문제 해결하기

f(lo, hi)가 될 수 있는 값은 1 ~ 100 사이의 숫자입니다. 따라서, 우리는 어떤 수열이든 1부터 100까지 모든 숫자를 하나씩 확인해보면 됩니다. 여기서 중요한 점은 바로 연속된 구간의 최대공약수 중 우리가 찾는 숫자 K가 있는지 확인하는 알고리즘입니다. 그럼 어떻게 해야 최대공약수가 K인 구간을 찾을 수 있을까요?

 

중요한 점은 바로 우리가 찾는 구간의 숫자들은 항상 K의 배수여야 한다는 점입니다. K의 배수가 연속으로 있는 구간에서만 최대공약수가 K로 나올 수 있으며, 만약 지금까지 탐색하는 구간의 최대공약수가 K가 나왔다면 탐색을 종료하면 됩니다. 자세한 알고리즘의 흐름을 한번 살펴봅시다.

 

만약, 현재 숫자가 K의 배수라면 어떻게 할까요? 그럼 K를 최대공약수로 가지는 구간일수도 있기 때문에 지금까지 구한 최대공약수와 현재 숫자와의 최대공약수를 구해야 합니다. 만약 현재 숫자가 처음으로 나온 K의 배수 혹은 구간의 시작점이라면 이 과정은 넘어갑니다. 이렇게 K의 배수를 만족하는 숫자들이 연속으로 나올 때에는 반복해서 최대공약수를 구하다가 최대공약수가 K가 나온 순간, 탐색을 종료하면 됩니다. 만약 K의 배수가 나오다가 중간에 K의 배수가 아닌 숫자가 나오면 어떨까요? 그런 경우에는 지금까지 구했던 최대공약수를 초기화하고 다음 숫자로 넘어가면 됩니다. 이렇게 수열 내 모든 숫자들을 하나씩 확인하면 우리가 원하는 f(lo, hi)가 나오는 경우의 수를 구할 수 있습니다.

 

좀 더 빠른 탐색을 위해 1부터 100 사이의 모든 숫자 간의 최대공약수를 먼저 구해놓으면 시간복잡도를 줄일 수 있습니다. memo[a][b] 배열을 사용하여 (a, b)의 최대공약수를 구하고 배열에 저장한다면 추후에 다시 똑같은 계산을 할 때, 빠르게 구할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <vector>
#include <deque>
#define NMAX 100010
#define AMAX 101
using namespace std;
 
int N, t;
vector< int > inp;
deque< int > dq;
 
int a, b, g, cnt;
int check[AMAX], memo[AMAX][AMAX];
 
int gcd(int a, int b) {
    if(memo[a][b] > 0) return memo[a][b];
    else {
        if(b == 0) return memo[a][b] = a;
        else return memo[a][b] = gcd(b, a%b);
    }
}
 
int main() {
    while(1) {
        // init
        cnt = 0;
        inp.clear();
        memset(check, 0, sizeof(check));
 
        // input
        scanf("%d", &N);
        if(N == 0) break;
        for(int i=0;i<N;i++) {
            scanf("%d", &t);
            inp.push_back(t);
 
            check[t] = 1;
        }
 
        // 배수 확인하기(1~100까지)
        for(int i=1;i<AMAX;i++) {
            if(check[i]) continue;
            dq.clear();
            g = 0;
 
            for(int num:inp) {
                if(num%i) {
                    dq.clear();
                    continue;
                }
 
                dq.push_back(num);
                if(dq.size() == 2) {
                    a = dq.front(); dq.pop_front();
                    b = dq.back(); dq.pop_back();
                    g = gcd(a, b);
 
                    dq.push_back(g);
                }
 
                check[g] = 1;
                if(g == i) break;
            }
        }
 
        // 출력
        for(int i=1;i<AMAX;i++) cnt += check[i];
        printf("%d\n", cnt);
    }
}

후기

구간 탐색과 약수 구하기가 어우러진 문제입니다. 빠른 계산을 위해 유클리드 호제법을 사용하고, 해당 결괏값을 배열을 사용하여 메모이제이션을 하는 건 처음 해보는 작업이라 무척 재미있었습니다. 약수를 활용한 심화 문제에 소개할만한 문제라고 생각합니다.