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

요구능력

최대공약수(유클리드 호제법)

 

문제풀이

아래는 프로그래머스의 예제그림이다.

이렇게 그림만보면 어떻게 풀어야할지 머릿속이 깜깜하다.

똑같이 생긴게 4개가 보인다.

w = 8, h = 12라고 했는데,

8,12랑 4가 연관이 있을까.. 생각해보면

최대공약수가 떠오르긴한다.

뭔가 확실한 해답은 아니니까 우선 넣어두고,

좌표가 (2,3), (4,6), (6,9), (8,12) 이렇게된다.

규칙성이 있는거같은데, 

한 부분만 똑 떼서 보면, w = 2, h= 3일 때

쓸 수 있는 사각형은 2개 쓸 수 없는 사각형은 4개이다.

(0, 0)에서 (2, 3)까지 가는데 가로로 2번가고 세로로 3번움직이면된다.

하지만, 가로로 2번가고 세로로 3번움직이면 사각형이 한번 겹친다.

그래서 X + Y - 1이라는 공식이 성립된다.

전체적에서 부분을 봤을때 이 한 부분은

(전체W/ 부분W) + (전체H/ 부분H) - 1로 구할 수 있고 아까 넣어 두었던 최대공약수만큼 패턴이 반복되는걸 생각해서 관련식을 만들어보면

(전체W/ 최대공약수 + 전체H/ 최대공약수) -1이 위의 그림의 부분적인 패턴의 사용할 수 없는 사각형의 개수를 구하는 식이다.

그럼 전체의 사용할 수 없는 사각형의 개수는 그 최대공약수를 그대로 곱해주면 된다.

그러면, 전체W + 전체H - 최대공약수 식이 나오게된다.

 

최대공약수는 유클리드호제법을 이용했다.

후기

규칙찾기..어렵네

 

코드

func solution(_ w:Int, _ h:Int) -> Int{
    func gcd(_ a: Int, _ b: Int) -> Int{
        var curA = a
        var curB = b
        while curB > 0{
            let temp = curA % curB
            curA = curB
            curB = temp
        }
        return curA
    }
    
    let answer:Int = (w * h) - ((w + h) - gcd(w, h))
    return answer
}