【프로그래머스】 멀쩡한 사각형 (Kotlin)

문제

프로그래머스

 

풀이

사용할 수 없는 정사각형을 표시해 보면 대각선을 따라 특정 패턴이 반복된다는 것을 확인할 수 있다.

이러한 패턴은 대각선이 정사각형의 꼭짓점과 만날 때마다 반복된다.

 

패턴을 포함하는 가장 작은 직사각형에서 사용할 수 없는 정사각형은 해당 직사각형의 가로 및 세로만큼 이동하므로 개수를 세면 총 

\(\mathbf{(w+h)/gcd(w, h)-1}\)개임을 확인할 수 있다.

이 패턴이 \(\mathbf{gcd(w, h)}\)번 반복되므로 전체 직사각형에서 사용할 수 없는 정사각형의 개수는 총 \(\mathbf{w+h-gcd(w, h)}\)개다.

 

최대공약수는 유클리드 호제법을 구현한 재귀함수를 사용하여 구한다.

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

코드

GitHub - blacksg/ProblemSolving

class Solution {
    fun solution(w: Int, h: Int): Long {
        val lw = w.toLong()
        val lh = h.toLong()
        return lw * lh - (lw + lh - gcd(w, h))
    }
    
    fun gcd(a: Int, b: Int): Int {
        if (b == 0) return a
        return gcd(b, a % b)
    }
}