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

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

 

입력 & 출력

가로의 길이 W와 세로의 길이 H가 주어질 때,
사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

풀이

두 방법을 생각했다
하나는 사각형을 더 만들어 규칙이 존재하는지 찾아보는 것이고
다른 하나는 비율에 따른 삭제되는 사각형의 개수를 찾는 것이다
전자의 방법으로 풀어보자

4, 4 사각형의 경우 4 개가 빠진다
2, 3 사각형인 경우 4 개가 빠진다
9, 3 사각형의 경우 9 개가 빠진다

한 눈에 봐서는 규칙을 찾기 힘들다..
삽질을 하며 찾아보았는데 최대 공약수를 구하고 사칙연산을 하니 한 규칙을 찾게 되었다
w과 h의 최대 공약수를 구해 w + h 에서 빼주면 삭제되는 수를 구할 수 있었다
남아있는 사각형의 개수는 w * h - (w + h - g) 식을 따른다

 

Swift 전체 코드

func solution(_ w:Int, _ h:Int) -> Int64 {
    func gcd(_ a : Int, _ b : Int) -> Int{
        if a % b == 0 {
            return b
        }
        return gcd(b, a % b)
    }
    
    return Int64(w * h - (w + h - gcd(w,h)))
}