프로그래머스 멀쩡한 사각형

완벽하게 다 맞는게 하나도 없네..

 

다른 사람 코드를 봄

class Solution {
    fun gcd(a: Int, b: Int): Long {
        if (a==0) return b.toLong()
        return gcd(b%a,a)
    }

    fun solution(w: Int, h: Int): Long {
        var wl = w.toLong()
        var hl = h.toLong()
        return wl*hl-wl-hl+gcd(w,h)
    }
}

최대 공약수를 저렇게 구하는 구나

 신기함

 

coding-factory.tistory.com/599

[Algorithm] 유클리드 호제법 - 최대공약수(GCD) 구하기

 

내 논리부터 틀렸던데

그냥 최대공약수를 나눠준 너비와 길이의 값을 더하고 -1을 하면 된다는데 왜그렇지??

 

 

--> 단순하게 생각해보면 a*b크기의 (a,b 는 서로소) 직사각형에서는 꼭지점을 시작지점과 끝지점만 지나므로 항상 하나의 정사각형을 지나갈 수 밖에없으므로  출발점 (0,0) 에서 도착점 (a,b)까지 계속해서 하나의 정사각형을 쌓으며 지나감.

그니까 

이런식으로 줄을 그어보면 결국 가로 + 세로 -1 개의 사각형을 지나가게 되있음  ㅇㅇ