[알고리즘 / 프로그래머스] 멀쩡한 사각형

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

코딩테스트 연습 - 멀쩡한 사각형

 

문제는 위와 같으며, 이 문제는 최대 공약수를 이용하여 문제를 해결할 수 있습니다.

 

예제를 통해 살펴보면 w = 8, h = 12 일 때, 대각선을 그으면 아래와 같이 작은 직사각형 패턴이 생기는 것을 알 수 있습니다.

작은 직사각형의 크기를 보면 w, h 를 최대 공약수로 나눈 것임을 알 수 있습니다.

 

따라서 유클리드 호제법을 통해 최대 공약수(GCD) 를 구한 뒤, 작은 직사각형의 크기를 구하면 가로 = w / GCD, 세로 = h / GCD 가 되고 이 작은 직사각형 안에서 잘린 사각형의 수는 작은 직사각형의 가로 + 작은 직사각형의 세로 - 1 이 됩니다. 전체 직사각형에서 작은 직사각형은 GCD 만큼 포함이 되기 때문에 결론적으로 전체 정사각형의 수 (w*h) - 잘린 직사각형의 수 ((w / GCD + h / GCD - 1) * GCD) 가 됩니다.

 

파이썬 코드는 다음과 같습니다.

def solution(w,h):
    answer = 1
    
    def get_gcd(a, b):
        while b:
            a, b = b, a % b

        return a


    gcd = get_gcd(max(w, h), min(w, h))
    mw = w // gcd
    mh = h // gcd

    answer = (w * h) - ((mw + mh - 1) * gcd)
    return answer

 

자바 코드는 다음과 같습니다.

class Solution {
    public long solution(int w, int h) {
        long answer = 1;
        
        int a = Math.max(w, h);
        int b = Math.min(w, h);

        while (b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }

        answer = ((long) w * (long) h) - (((long) w / a + (long) h / a - 1) * a);
        return answer;
    }
}