August 6, 2021

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

해법 : https://hyem-study.tistory.com/45

공식은 w+h-(w과h의 최대공약수)

공식 유도를 위한 설명

w×h 사각형에서 w과 h의 최대공약수가 a라고 할 때

w = abh = ac라고 합시다. (b,c는 당연히 서로소)

w×h 사각형은 a²개의 b×c 사각형으로 분할할 수 있고 대각선이 지나가는 b×c 사각형은 a개입니다.

b,c가 서로소이므로 b×c 사각형에서 대각선이 지나가는 단위사각형은b+c-1이고

w×h 사각형 전체적으로 보면 a(b+c-1) = ab+ac-a = w+h-a 입니다

코드

const gcd = (a,b) => {
    while(b>0) {
        let tmp = b;
        b = a%b;
        a = tmp;
    }
    return a;
}

function solution(w, h) {
    var answer = 1;
    
    return w*h - (w + h - gcd(w,h))
}

문제 설명