프로그래머스 코딩테스트 - 연습문제 - 멀쩡한 사각형

문제 출처 : 프로그래머스/연습문제/멀쩡한 사각형

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

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

풀이

class Solution {
    //2. 유클리드 호제법을 이용해서 최대공약수를 구한다.
    public long gcd(long idx1, long idx2) {
        while(idx2 > 0) {
            long tmp = idx1;
            idx1 = idx2;
            idx2 = tmp % idx2;
        }
        return idx1;        
    }
    
    public long solution(long w, long h) {
        long r = 0;
        //1. 숫자의 대소관계에 따라 다르게 메소드에 값을 넣는다.
        if(w > h) 
            r = gcd(w, h);
        else
            r = gcd(h, w);
        
        //3. 전체 갯수 - (가로 + 세로 - 가로세로의 최대공약수)를 하면 멀쩡한
        //사각형의 갯수가 나온다.
        return (w * h) - ((w + h) - r);
    }
}

이번 문제는 직사각형에서 그어진 선이 지나가는 사각형을 제외한 멀쩡한 정사각형을 찾아내야 하는데 

한가지 공식을 적용하면 사각형의 갯수를 구할 수 있다. 

 

예를들어 

8 X 12일때 96개의 정사각형중 선이 지나가는 사각형은 16개로 멀쩡한 사각형의 갯수는 80개가 나온다.

4 X 4일때 16개의 정사각형중 선이 지나가는 사각형은 4개로 멀쩡한 사각형의 갯수는 12개가 나온다.

1 X 8일때 8개의 정사각형중 선이 지나가는 사각형은 8개로 멀쩡한 사각형의 갯수는 0개가 나온다.

4 X 6일때 24개의 정사각형중 선이 지나가는 사각형은 8개로 멀쩡한 사각형의 갯수는 16개가 나온다.

여기서 선이 지나가는 사각형의 규칙은 (가로 + 세로 - 가로세로의 최대공약수)이다.

 

이때 최대공약수를 구하는 공식으로 유클리드 호제법이라는 알고리즘을 사용하면 된다.

유클리드 호제법은

1. 두 수중 큰수와 작은수를 구분한다.

2. 두 수를 나눈 뒤 나온 나머지를 다시 작은수와 나눠서 또 다시 나머지를 구한다.(계속해서 작은 수와 나머지를 나눈다.)

3. 나머지가 0이 되는 순간 큰수가 최대공약수이다.