[프로그래머스] 멀쩡한 사각형 - JAVA

문제

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

프로그래머스

 

코드

풀이1.

문제의 예제 그림을 회전시키면 보기 쉽게 바꿀 수 있다.

패턴이 반복되어 나타나므로 패턴을 잘라 자세히 살펴보자

패턴을 잘랐을때의 가로를 W', 세로를 H'라고 해보자.

W'가 1 증가할 때마다 흰사각형이 1 증가하는 것을 확인할 수 있다.

또한, 선이 가로선을 지날때 흰사각형이 1 증가한다. 가로선의 개수는 H' - 1 이 된다.

즉, 이를 식으로 나타내면 W' + H' - 1이 된다.

W'와 H'는 최대공약수를 이용하여 구할 수 있다.

 

class Solution {
    public long solution(int w, int h) {
        long answer = (long)(w)*(long)(h);
        if(w < h) {
            int temp = h;
            h = w;
            w = temp;
        }
        long mod = gcd((long)w, (long)h);
        long wratio = (long)w / mod;
        long hratio = (long)h / mod;
        
        long cut = wratio + hratio -1; 

        cut = cut * mod;            
        answer = answer - cut;
        
        
        return answer;
        
    }
    
    public long gcd(long a, long b){
        if(b==0) return a;
        return gcd(b, a%b);
    }
    

}

 

풀이 2.

그냥 단순하게 그래프에서 기울기 구하듯이 하면 된다.

class Solution {
    public long solution(int w, int h) {
        long answer = 0;
        double line = (double)h/(double)w;
        for (long i = 1; i < w; i++) {
            answer+=(h*i/w);
        }
        return answer*2;
        
    }
    
}