2/9기록 - 백준 1934

오늘은 교육이 있어서 아침에 급하게 문제를 하나 풀어보기 위해서 그래도 익숙한 문제를 하나 선정했다.

 

오늘의 문제는 최소공배수 문제이다. 최소공배수는 해당 두개의 값을 곱하고 최대공약수로 나누어 주면 간단히 해결할 수 있다. 하지만 최대공약수를 구할 때 알고리즘을 생각하지 않으면 굉장히 험난한 길을 갈 수도 있다. 

 

중딩때 경시대회 준비를 하면서 배웠던 유클리드 호제법을 아직도 최대공약수 구할 때 익숙하게 사용했었는데, 유클리드 호제법을 사용하면 최대공약수를 컴퓨터 언어로도 굉장히 쉽게 풀어낼 수 있다.

 

출처 : 위키백과

 

위키 백과에 유클리드 호제법을 잘 설명해 두어서 가져와 보았다. a와 b의 최대공약수를 (a,b)라 하면 (a,b) = (b,r) 로 표현하여 r 나머지가 0이 될 때까지 계속 나누어 준다. r이 0이 되는 순가 b 자리에 있는 값이 최대공약수가 된다.

 

알고리즘 생각

1. 값을 입력받기

2. 유클리드 호제법을 사용하여 최대공약수를 구하는  함수 만들기

3. 최소공배수 = (a*b)/a,b의 최대공약수

4. StringBuilder를 사용하여 반복문의 최소공배수값을 모두 append

5. 출력

 

 

최대공약수를 구하는 함수 GCD를 나누는 값 b가 0이 아닐 때 계속 GCD(b,r)로 해주기 위해서 재귀함수 형식으로 표현했고 b가 0이 되면 더이상 나눌 수 없으므로 a를 반환

 

이렇게 쉽게 최소공배수를 구해낼 수 있었다.

 

2/9 기록 끝!!!!!!!!