[EPPER] 10회 1번

문제

 

 

 

---

풀이

 

a, b를 입력받고 둘 사이의 최대 공약수를 구하는 문제이다. 원래는 유클리드 호제법을 사용하는게 정석이겠지만...난 너무 귀찮았다.

a<=b가 되도록 설정하고, a 자체가 최대 공약수가 될 수 있을지 한 번 체크한다. a가 최대 공약수가 아니라면 최대 공약수가 될 수 있을 가장 큰 수는 a/2일테니 그때부터 반복문을 돌려서 최대 공약수 여부를 확인한다. 그래도 절반으로 줄인 것에 의의는 있지 않을까...

그래도 일단 블로그에 글을 쓰고 있으니 유클리드 호제법으로 푸는 방법도 적겠다.

int gcd(int a, int b){
    if(b==0)
    	return a;
    else
    	return gcd(b, a%b);
}

원리는 정수론, 이산수학 등을 배우면 알 수 있다.

---

소스코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int a, b;

	scanf("%d %d", &a, &b);
	if (a > b) { //a가 더 작도록
		int tmp = a;
		a = b;
		b = tmp;
	}
	if (b % a == 0) //a가 최대공약수인지 확인해보고
		printf("%d\n", a);
	else {
		for (int i = a / 2; i >= 1; i--) { //a 나누기 2 부터 검사
			if (b % i == 0 && a % i == 0) {
				printf("%d\n", i);
				break;
			}
		}
	}
}