백준 1850번[c/c++] : 최대공약수

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

1850번: 최대공약수

---

풀이

풀이에 앞서 프로그래밍에서 최대공약수를 구하는 함수를 알아보자(gcd 알고리즘)

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

예시로 gcd(8,24)를 생각해보자.

b가 0이 아니기 때문에 재귀함수 gcd(24,8)이 호출된다.

gcd(24,8)도 b가 0이 아니기 때문에 재귀함수 gcd(8,0)이 호출된다.

gcd(8,0)의 b가 0이기 때문에 a의 값이 리턴된다.  a의 값은 최대공약수 8이다.

 

반복문을 사용하여 최대공약수를 구할 수 있지만 a가 b보다 항상 커야 한다는 조건식이 붙기 때문에 재귀함수 식을 사용하였다.

 

 

문제의 예시를 보면

1. 첫번 째 예시의 최대공약수는 1이다.

2. 두번 째 예시의 최대공약수는 3이다.

3. 세번 째 예시의 최대공약수는 2이다.

gcd함수를 실행시키면 최대공약수를 확인할 수 있다.

 

예제 입력의 최대공약수를 보면 규칙을 찾을 수 있다.

최대공약수 수만큼 1이 반복되어있는 것을 확인할 수 있다.

즉 A와 B의 최대공약수를 구한뒤 그 수만큼 1을 출력해주면 된다.

 

c언어

#include<stdio.h>
long long int gcd(long long a,long long b) {
	if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}
int main() {
	long long result = gcd(3,6);
	long long a, b;
	scanf("%lld %lld", &a, &b);
	long long answer = gcd(a, b);
	for (int i = 0; i < answer; i++) {
		printf("1");
	}
	
	return 0;

}

 

c++

#include <iostream>
using namespace std; 
long long int gcd(long long a,long long b) {
	if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}
int main() {
	long long result = gcd(3,6);
	long long a, b;
	cin >> a >> b; 
	long long answer = gcd(a, b);
	for (int i = 0; i < answer; i++) {
			cout << 1; 
	}
	return 0;

}