[프로그래머스] 코딩테스트 연습 Summer/Winter Coding(2019) 멀쩡한 사각형 with Swift

안녕하세요. 오늘은 프로그래머스 멀쩡한 사각형 문제를 풀어보겠습니다!

 

이 문제 풀다가 머리가 터질뻔했는데요...

 

중고딩때 도형문제를 더 공부했더라면 수월하게 풀었을듯합니다 ㅠㅠ

 

결과적으로 보면 풀이가 참 간단합니다!

 

우선 서로가 최대공약수가 없는 도형(가로지르는 선이 정수인 n,m의 (n,m)인 지점을 지나게 하지 않기 위해)에서 w+h-1이 망가지는 도형의 수이다!

 

그러므로 최소공배수를 구해 도형을 쪼개고 w+h-1을 구하고 최소공배수를 다시곱해 전체 블록의 갯수에서 빼시면 문제를 해결하실 수 있습니다!

 

import Foundation

func gcd(_ a: Int64, _ b: Int64) -> Int64 {
    if b == 0 {
        return a
    } else {
        return gcd(b, a%b)
    }
}

func solution(_ w:Int, _ h:Int) -> Int64{
    var answer:Int64 = 0
    
    if w == h {
        answer = Int64(w)
        answer = Int64(w) * Int64(h) - answer
        return answer
    }
    else {
        var longLine = w > h ? Int64(w) : Int64(h)
        var shortLine = w < h ? Int64(w) : Int64(h)
        
        // GCD
        var GCD = gcd(longLine, shortLine)
        
        answer = shortLine / GCD + longLine / GCD - 1
        answer = Int64(w) * Int64(h) - answer * GCD
    }
    return answer
}