[C언어 백준 풀이][Bronze III] 유클리드 호제법 응용, 큰 수 나누기 (백준 1837번 : 암호 제작)

문제

1837번: 암호제작

 

백준 1837번 : 암호 제작 문제를 풀이해봅시다.

이번 문제에서 필요한 기술과 개념은 long long int를 벗어나는 큰 수 다루기, 유클리드 호제법입니다.

링크는 위에 첨부되어 있습니다.

 

 

어떤 자연수와 특정 K값에 대해, 이 자연수가 K보다 작은 소수로 나누어떨어지지 않는지 확인하는 문제입니다.

 

 

입력 / 출력 / 예제

 

입력 범위가 정수 크기 이내라면 일일이 반복문을 돌려 확인해보면 되겠지만, 이 문제에서는 자연수 P가 10^100 이하인 long long int 범위를 벗어나는 입력이 주어집니다.

따라서 수 전체를 한 번에 연산할 수 없으며, 수 전체에 대한 연산이 불가능합니다.

그러므로 여기서는 자릿수의 일부만 가지고 연산을 하여 나누어떨어지는지를 판별할 수 있는 유클리드 호제법을 사용해야 합니다.

 

 

유클리드 호제법

유클리드 호제법 : 두 양의 정수 a, b에 대해 a = bq + r일 때, a와 b의 수의 최대공약수는 b와 r의 최대공약수와 같다.

 

유클리드 호제법이란 두 양의 정수를 가지고 최대공약수를 빠르게 구하는 방식입니다.

 

ex ) 472와 38의 최대공약수를 구해봅시다.

472 = 38 * 12 + 16

38 = 16 * 2 + 6

16 = 6 * 2 + 2
6 = 2 * 3 + 0

 

여기서 나머지가 더 이상 발생하지 않으므로 472와 38의 최대공약수는 2임을 알 수 있습니다.

 

ex ) 37과 5의 최대공약수를 구해봅시다.

37 = 5 * 7 + 2

5 = 2 * 2 + 1

 

나머지가 1이 나왔으므로 37과 5의 최대공약수는 1이고, 따라서 둘은 서로소임을 알 수 있습니다.

 

두 수의 최대공약수를 구하는 가장 기초적인 방법은 2부터 시작해서 공약수인지를 일일이 판별하는 것이지만, 이 방법으로 프로그래밍 문제를 해결할 경우 제한 시간안에 처리하기가 불가능한 경우가 있고, 또 큰 수를 다루어 나눗셈을 할 수가 없다는 한계점이 있습니다.

유클리드 호제법을 이용할 경우 이 두 가지 문제의 해결이 가능합니다.

 

 

유클리드 호제법의 응용

유클리드 호제법의 원 성질은 매우 유명하기 때문에 잘 알려져 있습니다.

이 문제에서는 그보다도 응용이 더 중요한데, 그것은 다음과 같습니다.

 

1. a의 앞 자리수부터 1자리씩 꺼내와서 b로 나눈 나머지를 구한다.

2. 다음 자리수가 있을 경우 10을 곱하고 a의 다음 자리수를 꺼내와서 더한다.

3. 1~2를 반복하여 a의 모든 자리수에 대한 연산이 끝났을 때 0이 얻어지면 a는 b로 나누어떨어진다.

 

이 성질을 이용하면 이 문제를 아주 쉽게 해결할 수 있습니다.

 

 

풀이

#include<stdio.h>
#include<string.h>

int main() {
    char P[101];
    int K, isPrime, num, key = 1000001;
    scanf("%s %d", P, &K);
    for(int i=2; i<=K; i++) {
        isPrime = 1;
        for(int j=2; j*j<=i; j++) if(i%j == 0) { isPrime = 0; break; }
        if(!isPrime) continue;
        num = 0;
        for(int j=0; j<strlen(P); j++) num = (num*10 + P[j] - '0') % i;
        if(!num) { key = i; break; }
    }
    if(key < K) printf("BAD %d", key);
    else printf("GOOD");
}

 

풀이는 위와 같습니다.

우선 정수를 입력받는 과정에서만 하더라도 long long int의 범위를 벗어나므로, 이전 포스트에서도 다뤘던 "문자열로 정수 입력받기"를 이용하여 입력을 받은 뒤, 문자열로써 수를 처리해주어야 합니다.

그 다음 i를 증가시켜가며 K 이하에서의 모든 소수들을 찾은 뒤, 각 소수들에 대해 유클리드 호제법 응용을 사용해줍니다.