[프로그래머스] 멀쩡한 사각형 / 최대공약수, 유클리드 호재법

문제

 

풀이

#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;

long long solution(int w,int h) {
    long long answer = 1;
    long long a = min(w,h);// 최대공약수 (모서리 모서리로 이어지는 네모의 개수)
    for(; a>0; a--){ 
        if(w%a == 0 && h%a == 0) break;
    }
    long long ws = w/a, hs = h/a;
    return answer = (long long)w*h - (ws + hs - 1)*a;
}

처음엔 최대 공약수를 int값으로 구했기 때문에 오류가 발생했다.

범위 오류가 생길 수 있기 때문에 long long 인지 int인지 잘 보고 구할 것!

 

 

최대공약수를 사용하는 이유

우선 w와 h가 공약수가 있다면 문제를 공약수를 나눈 w'와 h'로 축소시킬 수 있다.

w'와 h'가 서로소(1 이외에 공약수를 갖지 않는 둘 이상의 양의 정수)라 가정했을 때 대각선은 반대쪽 코너에 도달하기 전 w'-1 세로선과 h'-1 가로선을 지나고 지날 때마다 새로운 정사각형이 추가된다.

 

즉 첫 정사각형을 포함 1 + (w'-1) + (h'-1) = w' + h' - 1개의 정사각형을 지나게 되고, 공약수를 다시 곱해주면

w + h - gcd(w, h) 개의 정사각형을 지나는 것을 찾을 수 있다.

 

따라서 다음이 성립한다

깨진 사각형의 개수 = w(가로) + h(세로) - gcd(w, h)(가로 세로의 최대공약수) 

 

 

---

 

다른 사람 풀이

#include <iostream>
using namespace std;

int GCD(int a, int b){
    if(a == 0) return b;
    return GCD(b % a, a);
}

long long solution(int w,int h)
{
   long long answer = 1;

    int gcd = GCD(w, h);
    cout << w + h - gcd;
    answer = ((long)w * h) - ((long)w + h - gcd);

   return answer;
}

 

GCD

• 유클리드 호재 법으로 최대공약수를 구하는 알고리즘

 

좌) 내 코드 실행시간 / 우) 유클리드 호재법 실행시간

숫자가 커질 경우 유클리드 호재법으로 푼 것이 for문을 이용하여 최대공약수를 구하는 방법보다 실행시간이 더 빠르다.

 

 

 

최소공배수(LCM)  

-최소 공배수 역시 GCD를 사용하여 쉽게 구할 수 있다. 

int GCD(int m, int n) {
  if (m % n == 0) return n;
  return GCD(n, m % n);
}

(m * n) / GCD(m, n)  // m과 n의 최소공배수

 

 

 

 

---

https://jacobgrowthstory.tistory.com/31

[알고리즘] 유클리드 호제법 : 최대공약수(GCD)와 최소공배수(LCM)

https://programmers.co.kr/questions/11306

프로그래머스