[알고리즘 수학] n일장이 함께 열리는 날짜는 언제일까요?

길동이가 사는 마을은 7일에 한번씩 장이 열립니다.

즉 1일에 장이 열렸다면 그 다음 장은 8일에 열립니다.

원당이가 사는 마을은 5일에 한번씩 장이 열립니다.

즉 1일에 장이 열렸다면 그 다음 장은 6일에 열립니다.

길동이가 사는 마을과 원당이가 사는 마을에서 오늘 장이 열렸습니다.

그렇다면 몇일 후에 길동이가 사는 마을과 원당이가 사는 마을에서 같은 날짜에 장이 열릴까요?

 

문제풀이)

이 문제는 5와 7의 최소 공배수를 찾는 문제입니다.

최소 공배수를 찾는 알고리즘은 a * b / 최대공약수(a,b) 입니다.

최대공약수를 찾는 알고리즘은 유클리드 호제법을 이용해서 a와 b의 최대 공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다고 정의 할 수 있습니다.

따라서 최대공약수를 구하는 알고리즘을 C언어로 풀어 보면 다음과 같습니다.

int gcd(int a,int b)
{
	if(a%b==0) return b; //a가 b로 나눠 떨어진다면 b가 최대공약수
    return gcd(b,a%b); // 아니라면 a,b 의 최대공약수는 b,a%b와 같다.
}

최소공약수를 구하는 알고리즘을 C언어로 풀어 보면 다음과 같습니다.

int lcm(int a,int b)
{
	return a*b/gcd(a,b);
}

 

위의 문제를 알고리즘에 의해 해결하려면 5와 7의 최대 공약수는 7과 5의 최대공약수와 같고

7과 5의 최대공약수는 5와 2의 최대공약수와 같고

5와 2의 최대공약수는 2와 1의 최대공약수와 같으므로 최대공약수는 1입니다.

따라서 최소공배수는 7*5/1 =35 입니다.

 

정답은 35일 후에 다시 두 마을에서 같은 날 장이 열립니다.