[알고리즘] 프로그래머스 멀쩡한 사각형 -Summer/Winter Coding(2019)-

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

프로그래머스

 

 

 

프로그래머스 멀쩡한 사각형이라는 문제를 풀어봤습니다.

30분 정도 풀다가 사각형에서 자도 없어서 대각선 그려서 사각형 몇개 지나는지 그리거나 보기도 힘들고 기울기 방정식이나 분할해서 계산, 규칙 등 계속 볼려고 했으나 모르겠어서 바로 구글링했습니다. 허허

출처: https://m.blog.naver.com/PostView.nhn?blogId=zzinuhelios&logNo=120024685950&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

 

그렇답니다. 설명은 사이트 들어가면 자세히 나와있습니다. 공식을 아니 최대공약수만 구할 줄 알면 바로 풀리는 문제였습니다. 

 

이번 문제로 얻어간 거는 저러한 공식이 있다는거와 최대공약수 구하는 방법이였던 것 같습니다.

 

풀이는 다음과 같습니다.

class Solution {
    //대각선이 지나는 단위정사각형'에 대한 문제 중 직사각형의 각 변을 m,n이라고 할때 공식은 m+n-(m과n의 최대공약수)입니다.
    public long solution(long w, long h) {
        long answer = 1;
        long GCD = 1;
        if (w > h) {
            GCD = gcd(w, h);
        } else {
            GCD = gcd(h, w);
        }
        long passSquare = w + h - GCD;
        answer = w * h - passSquare;
        return answer;
    }

    public static long gcd(long big, long small) {
        if (big % small == 0) {
            return small;
        }
        return gcd(small, big % small);
    }
}

 

 

 

추가로 최소공약수도 알아봤습니다. 최대공약수에대해서도 써있습니다. 바로 써먹을 수 있게 외워놉시다.

출처: https://ggmouse.tistory.com/317

[JAVA] 백준 알고리즘 2609 : 최대공약수와 최소공배수