프로그래머스 - 멀쩡한 사각형

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 멀쩡한 사각형

https://programmers.co.kr/learn/courses/30/lessons/62048

풀이 1. (초급) - 기울기를 통해 멀쩡한 사각형의 기울기를 구하기

class Solution {
    public long solution(int w,int h) {
         long answer = 0;
	        for(int i = 0; i < w; i++) 
	        	answer += (Long.valueOf(h) * i) / Long.valueOf(w); // h/w : 직사각형의 기울기
        return answer * 2;
    }
}

풀이 2. (중급) - 최대공약수를 구하여 멀쩡한 사각형의 갯수를 구하기

class Solution {
    public long solution(int w,int h) {
        long min=Math.min(w, h);
        long max=Math.max(w, h);
        long remain=1;
        while(remain>0) { // 유클리드 호제법
            remain=max%min;
            max=min;
            min=remain;
        } // max : 최대공약수
        long answer = (long)w*(long)h-max*(w/max + h/max -1);
        return answer;
    }
}

> 유클리드 호제법_

큰 수 A를 작은수 B로 나누었을때 나누어 떨어진다면 최대공약수는 B가 된다.

1) 입력 받은 두 수중 큰 수를 A, 작은수를 B로 정한다.

2) A 를 B 로 나눈값의 나머지를 R로 지칭한다.

3) R 이 0이라면 A는 B로 나누어 지기 때문에 최대 공약수는 B가 된다.

4) 만약 R이 0이 아니라면 A값은 B로, B 값은 R로 변경한뒤 반복한다.