프로그래머스 - 멀쩡한 사각형(Java, LV2)

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

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

풀이

해당 문제는 사각형 패턴의 규칙을 찾는 것이 관건이었다.

(나는 3개의 예제를 그려보며 패턴이 있음을 파악했다... 수학적 사고가 뛰어난 사람들은 저게 1차함수를 활용하는 문제임을 알고 푼 듯하다)

 

먼저 대각선이 그어지는 패턴을 보면 어느 꼭짓점(좌표)에서 딱 맞게 떨어진다.

 

그림 출처 : ajufresh.log

빨간색 형태의 패턴이 반복 된다

그렇기에, 딱 꼭짓점에 맞아 떨어지는 사각형 패턴을 가지고 와서 보면 된다.  

즉, 저 빨간색 패턴만 두고 생각했을 때, 저 패턴 내에서 사용하지 못하는 사각형을 구하고 그 패턴이 몇개 나오는지를 계산하면 정답이 된다.

 

이 때, 패턴은 가로/최대공약수:세로/최대공약수 의 비율이 된다. 

나는 이 비율을 wg, hg로 선언했다. 해당 패턴을 가지고 와서 보면 다음과 같다.

 

대각선은 가로만큼 가고, 세로만큼 가기에 wg+ hg 만큼 사용하지 못한다.

이 때, 가로와 세로가 겹치는 시작부분이 꼭 1개 존재한다(1,1).

즉 wg + hg -1 만큼 사용하지 못하는 것이다.

 

정답은 w * h -(wg + hg -1)의 공식이 완성한다. 단, long 형을 주의한다. 

class Solution {
    // 최소공약수 구하기
    public int gcd(int a, int b){
        int temp;
        if (a>= b){
            temp = a;
            a = b;
            b = temp;
        }
        
        while(b!=0){
            temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
    public long solution(int w, int h) {
        long answer = (long)w* (long)h;
        
        // 배수 구하기
        long gcd_val = gcd(w,h);
        long wg = w / gcd_val ;
        long hg = h / gcd_val;
        
        long diff = gcd_val * (wg + hg -1);
        answer -= diff;
        
        return answer;
    }
}