길동이가 사는 마을은 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일 후에 다시 두 마을에서 같은 날 장이 열립니다.
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기
'강의자료 > 알고리즘 수학' 카테고리의 다른 글
[알고리즘 수학] 쪽번호 붙이기 (23) | 2023.03.23 |
---|---|
[알고리즘 수학] 팬 케이크 만들기 (15) | 2023.02.28 |
[알고리즘 수학] 두 날짜 사이의 기간 구하기 (7) | 2022.11.16 |
[알고리즘 수학] 등수 구하기 (8) | 2022.11.03 |
[알고리즘 수학] 쇼핑몰의 등급별 할인율을 계산해 주자. (5) | 2022.10.05 |