<Programmers> Lv2 유클리드 호제법, GCD, LCM_멀쩡한 사각형 c++
2060 단어 programmersGCDLCMalgorithmGCD
(12 x 8)
의 사각형에서 잘려나간 도형들은 모양을 반복하고 있는데 이 모양이 몇 번 반복되었는지 확인해본다
- 잘려나가는 도형이 외접하는 사각형
(3 X 2)
의 사각형이총 4번
반복됨을 알 수 있다 - 이는
12와 8의 최대공약수 4
로 각 값을 나누면3,2
가 된다는 사실을 알 수 있다. - 그리고 외접하는 사각형에서 실제로 잘려나간 사각형은
w*h-1
개 이다
여기서 최대공약수를 구하기 위해 유클리드 호제법을 이용한다
📍Euclidean algorithm
(참고: 위키피디아)
- 2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라고 한다 (a>b)
- a와 b의 최대 공약수는 b와 r의 최대공약수와 같다
- 이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고 다시 r을 r'로 나누는 과정 반복
- 나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대공약수
📍Greatest Common Divisor (GCD)
public static int gcd(int a, int b) { while (b>0) { int tmp=b; b=a%b; a=tmp; } return a; }
📍Least Common Multiple (LCM)
public static int lcm(int a, int b) { return (a*b) / gcd (a,b); }
📝Source Code
using namespace std; int getGCD(int a, int b) { while (b>0) { int tmp=b; b=a%b; a=tmp; } return a; } long long solution(int w,int h) { long long answer = 1; int gcd=getGCD(w,h); int mw=w/gcd; int mh=h/gcd; long long cut=(long long)mw+mh-1; cut*=gcd; answer=(long long)w*h-cut; return answer; }
Author And Source
이 문제에 관하여(<Programmers> Lv2 유클리드 호제법, GCD, LCM_멀쩡한 사각형 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Programmers-Lv2유클리드-호제법-GCD-LCM-멀쩡한-사각형-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)