[c언어] 백준 최대공약수 하나 빼기

코딩할때 가장 열받는 문제는 해석하기가 난해하다는 점이다. 코드 짜는것도 힘든데 문제가 뭔지 파악하는게 어려운 문제는... 더 짜증난다.

이 문제도 해석하는데 꽤 오랜 시간이 걸렸다. 

 

 

임의의 값 k를 뺐을 때, 그 값을 뺀 나머지 수들의 최대공약수가 K의 약수가 되면 안된다.

만약 정답을 구할 수 없다면 -1 을 반환하라.

 

 

사실 무슨 말인지 이해가 안가서 구글링을 했더니 최대공약수를 일일이 찾는것은 오랜 시간이 걸리기 때문에 ( n의 개수가 100만개까지 허용 )GCD 함수를 써야한다고 되어있었다. 

 

gcd란 (a<b) 이면, GCD(a,b) = GCD(b, a%b) 라는 성질이다.

b가 0이 되면 a값을 리턴한다. 

 

숫자 5개 입력했을때 8 12 24 36 48

leftgcd에는 8 , 4 , 4..

rigthgcd 에는 48, 12 , 12 , 12, 4

이렇게 저장을 하는 것이다.

각 gcd 배열에 들어가는 수가 입력숫자간의 최대공약수를 입력하면 된다. 

 

 

 

 

 

전체코드

#include <stdio.h>
int leftGcd[10000002];
int rightGcd[10000002];
int arr[10000002];

int gcd(int a, int b) {
	while (b != 0) {
		int r = a%b;
		a = b;
		b = r;
	}
	return a;
}


void main() {
	int n = 0;
	int num = 0;
    //4~1000000 개의 숫자 입력 가능.
	scanf_s("%d", &n);
    //n개 만큼의 숫자 입력 후 배열arr에 저장
	for (int i = 1; i <= n; i++) {
		scanf_s("%d", &num);
		arr[i] = num;		
	}
	leftGcd[1] = arr[1];
	rightGcd[n] = arr[n];
    
    //leftGcd에다가 왼>오 순으로 최대공약수를 넣는다. 
    
	for (int i = 2; i <= n; i++) {
		leftGcd[i] = gcd(leftGcd[i - 1], arr[i]);
	}
    
    //rightGcd에다다가 오>왼 순으로 최대 공약수를 넣는다. 

	for (int i = n - 1; i >= 1; i--) {
		rightGcd[i] = gcd(rightGcd[i + 1], arr[i]);
	}


    //ansGcd는 최대공약수 , ans 는 뺀 값 k를 나타낸다. 
	int ans = 0;
	int ansGcd = 0;
	for (int i = 1; i <= n; i++) {
		int Gcd = gcd(leftGcd[i - 1], rightGcd[i + 1]);

		if (arr[i] % Gcd != 0 && Gcd > ansGcd) {
			ans = arr[i];
			ansGcd = Gcd;
		}
	}
	if (ans == 0 && ansGcd == 0) {
		printf("\n-1");
	}
	else {
		printf("%d %d ", ansGcd, ans);
	}


	system("pause");

}