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

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

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

2021-07-16

---

public class Solution62048 {
    public static long solution(int w, int h) {
        long answer = 0;
        long wl = Long.parseLong(String.valueOf(w));
        long hl = Long.parseLong(String.valueOf(h));
        answer = (wl + hl) - gcd(wl, hl);
 
        return (wl * hl) - answer;
    }
 
    public static long gcd(long min, long max) {
        if(min > max) {
            long tmp = min;
            min = max;
            max = tmp;
        }
 
        while(min != 0) { // 유클리드 알고리즘, min값이 0이 될때까지 (max % min)을 돌고, min이 0이 되면 max값을 gcd로 판단한다.
            long tmp = max % min;
            max = min;
            min = tmp;
        }
        return max;
    }
 
    public static void main(String[] args) {
        int w = 8;
        int h = 12;
        System.out.println(solution(w, h));
    }
}

#문제풀이

처음에 규칙을 찾아보려고 했었는데, 답이 안 나와서 이 블로그에서의 (https://m.blog.naver.com/tlstjd436/221849619470) 최대공약수 아이디어를 참조하였다. 어려운 문제였다. 

 

우리는 사각형을 가로지르는 선을 그으면서 패턴을 발견할 수 있다. 그리고 이 패턴의 갯수를 셀 때 세로로 그리고 가로로 셀 수가 있는데, 이 때 겹치는 부분이 존재한다. 

 

세로로 센 갯수 + 가로로 센 갯수 - 세로/가로 겹치는 부분 이라는 공식을 만들 수 있는데, 이는 사각형의 가로길이 + 세로길이 - 가로와세로길이 사이의 최대공약수와 같다.

w == 4, h == 6

w == 6, h == 8