백준 C++ 2609번 최대공약수와 최소공배수 ( 유클리드 호제법 )

벌써 3월 끝자락이군요.

저는 요즘

석화지라는 중국드라마를 보고 있었는데

오늘 완결까지 다 봤습니다.

 

중국 고장극을 처음 봤는데

한국 사극이랑은 또 다른 매력이 있더라고요.

중국이라 그런지 건물도 엄청 으리으리해요....

옷도 한복은 아닌데.. 뭐랄까 개량한복 느낌.. 보단 고급진..

 

그리고 제가 본 드라마는 뭔가 무난 무난하게 흘러갔다고 해야 하나

반전도 크게 없었고,

속고 속이던 일도 오해 없이 잘 풀린..

해피엔딩이었습니다.

 

문제는

40화짜리인데도.. 또 보고 싶은...

ㅎㅎㅋㅋㅋ저는 파워 N이라 한번 보고는 잊을 수가 없네요.

계속 머릿속에 붕붕 떠다니는 거 있죠.

 

아직도 클립을 계속 돌려보고 돌려보는 중..

얼른 다시 보던지, 새로운 다른 드라마를 찾아야겠어요.

ㅎㅎㅎㅎ

---

 

 

석화지 ost를 들으며 문제를 푸는 중

 

나는 어렸을 때 최소공배수와 최대공약수를 ㄴ 으로 풀었는데 말이다.

 

예전에는 그렇게 풀었는데 말이다...

이걸 컴퓨터한테 어떻게 알려줘야 할지....ㅋㅋㅋ

 

결국 인지 씨를 찾아갔다.

 

사실 그 내장 라이브러리가 존재할 거 같아서 물어봤는데

도전과제에 맞게 문제를 풀어보라고 했다..

 

긁적.

 

그리고 

재미난 정보를 알려주었다.

 

두 식을 곱한 값이랑 최대공약수 * 최소공배수랑 같다고 한다!!

 

그리고 최대공약수를 구하는 방법에

전설적인 알고리즘이 존재한다고 한다.

 

그것은 유클리드 호제법!!

이게 뭐인가!!

 

유클리드 호제법은

"큰 수를 작은 수로 나눈 나머지를 구하고, 나머지가 0이 될 때까지 이 과정을 밀어내기 하듯 반복한다!"

 

쉽게 설명해 달라고 했더니 쉽게 설명해 주었다.

 

색종이라고 생각하고

위에 식 24 18 이 있다면

24cm짜리 색종이 18cm짜리 색종이 

이렇게 두 개를 가지고

가장 큰 정사각형을 여러 개 쪼개는 것!!

일단 18이 가장 크겠죠?

 

24 % 18 해주고

그럼 답이 6이 나온다.

 

그럼 18*18 짜리 하나 18*6 짜리 하나가 나오게 된다.

그럼 18 * 6을 가지고 또 가장 큰 정사각형을 잘라본다.

6*6으로 해야 하니

18%6을 해준다.

그럼 답이 0이 나온다.

즉 6*6 3개가 나오고 끝나는 것!

나머지가 0이 됐다는 것은 이제 더 이상 자를 게 없으니

6이 가장 큰 정사각형으로 쪼갤 수 있게 된다.

 

오케이! 계속 위치를 당기면서 나누고

그 값이 0이 되면 나눈 수가 답이 되겠지요.

 

그것이 바로 최대공약수 되시겠다!

 

 

자잔!

완성!

 

이제 합법적인 치트키..

라이브러리를 공부해 보자!!

 

먼저 헤더가 필요하다.

#include <numeric>

이라고 한다.

<bits/stdc++. h>를 쓴다면? 안 써도 된다.

 

그다음에 

최대공약수

gcd는

gcd(a, b)이렇게 써주면 되고

최소공배수

lcm은

lcm(a, b)로 써주면 된다.

 

 

단 두줄이면 끝나는 식..

 

이 라이브러리는 C++17부터 사용이 가능해서

그 이상으로 언어를 설정해 줘야 맞다고 통과가 된다고 합니다!

유의해주세요!!

 

---

오케이

 

무엇보다,

최대공약수, 최소공배수의 경우의 패턴을 익혔다는 것이 

오늘의 배운 점과 뿌듯한 점이다.

 

휴!

이제 또 석화지 1화 보러 가볼까아아아