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

https://programmers.co.kr/learn/courses/30/lessons/62048

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

level 2 구현 (최대공약수 & 수학)

 

 직사각형의 가로,세로 크기가 주어지고, 이 직사각형을 구성하는 넓이가 1(1*1) 사각형 중에 대각선이 지나가는 사각형을 제외한 작은 사각형들의 넓이의 합을 반환하는 문제이다.

 

접근방법

간단해 보였는데 어려웠다.

우선 대각선이 사각형들의 꼭짓점과 만나는 점을 기준으로 작은 사각형으로 분리해야 했다.

이 작은 사각형을 구하려면 w,h의 최대공약수를 구해야 한다.

최대공약수를 구하는 방법은 단순히 둘 중 작은 수부터 1씩 감소해가며 최대공약수가 맞는지 확인하는 방법으로도

현재 테스트 케이스는 통과되긴 한다.

풀이는 유클리드 호제법을 사용했다. 유클리드 호제법은 두 양의 정수 a,b에 대해 a % b = r ( a < b ) 일 때, gdc(a, b) = gcd(b, r)이 성립한다는 것.

귀류법 증명이 위키백과에 있긴한데 따라서 증명해보다가 귀류법이어서 완전히 납득가지는 않은 채로 나옴 (귀류법 증명은 어느 부분을 모순으로 만들어야할지 모르겠어서 어렵다) 똑똑한 수학자들..

 

최대 공약수를 구하고 난 후에 구할 수 있는 작은 사각형(w'*h')에서 대각선이 지나는 사각형을 구하는 식은

w' + h' - 1  이다. 찾아보니까 귀납법으로 식을 도출한 걸 많이 봤는데 정확한 원리는 모르겠다~!

식을 알기 전에는 기울기를 사용해서 y = (h'/w')*x로 두고 x축의 좌표 1 ~ w'-1 까지에 대해 y값 내림을 누적합해줬다.

그랬더니 런타임오류와 함께 dump오류가 나왔던 것 같다. 아무래도 크기 제한이 1억이라 시간초과가 걸릴 것 같긴 했는데

완전히 이해되지는 않는 식으로 귀납법이려니~!하고 풀어냈다~!

 

끝~!

소스코드

import Foundation

func solution(_ w:Int, _ h:Int) -> Int64{
    var answer:Int64 = 0
    
    var a:Int = max(w,h)
    var b:Int = min(w,h)
    var r:Int = b
    
    while b > 0 {
        r = a % b
        a = b
        b = r
    }
    let gcd:Int = a
    
    let entireArea:Int64 = Int64(w*h)
    answer = entireArea - Int64(w + h - gcd)
    return answer
}

 

2022.03.02 기준