멀쩡한 사각형 , 패턴을 찾자. gpt : GCD 한줄 처리

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

프로그래머스

 

다각선의 블록을 제외한 나머지의 넓이를 구하는 문제이다.

 

사용가능한 블록의 패턴을 찾기 위해서 시도했으나, 실패를 했다. , 최대 공약수가 힌트가 될것이라는 직관이 어느정도 나왔지만, 모눈 종이의 도움없이는 증명이 어려웠다.

 

사용 불가능한 넓이를 한번 고려를 해봐야한다.

전체 넓이 = 사용 가능 + 사용 불가 이기 때문이다.

 

-> 사용 불가능한 넓의 패턴 =  주어진 사각형의 가로 세로의 최대 공약수의 패턴 

 

 

 

class Solution {
            // answ = all -  (w + h  - GCD(w,h))
        public long solution(int w, int h) {
            return (long) w * h - ((long) w + h - gcd(w, h));
        }

        public int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }

}

gpt 의 gcd 함수 알고리즘이다.

1. a 나 b 중 하나가 0이라면 , 알고리즘은 즉시 종료가 된다.

2.  큰수는 작은수로 나눈 나머지로 대체가 되므로

큰수는 절반 이상으로 줄어든다.

 

유클리드 알고리즘의 시간 복잡도는 O(logmin(a,b))로, 매우 효율적입니다.

 

 

public int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}