Algorithm - lev2 - 멀쩡한 사각형

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

풀이

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

let greatestCommonDivisor = (a, b) => {
    while(b > 0){
        let r = a % b;
        a = b;
        b = r;
    }
    return a;
}

• 이 문제는 풀지 못했다. 다른 사람 블로그에 잘 정리된 글이 있어서 참고했다.
• 먼저 이런 문제를 풀 떄 수학적 배경이 없다면 유심히 봐야할 부분은 반복되는 부분에서 힌트를 얻을 수 있다, 반복된다는 것은 내가 신경써야할 범위를 좁힐 수 있다는 것이고, 반복 패턴만 알아낸다면 답을 구하는 건 어렵지 않다.

참고 자료

• 이번 문제에서는 x,y축으로 놓고 보았을 때 x축은 2마다, y축은 3마다 반복되는 패턴을 확인할 수 있다.
• 이는 가로 8과 세로 12의 최대공약수인 4로 각각을 나누었을 때를 의미하며, 2*3 사각형에서 잘려나가는 사각형의 갯수는 x+y-1이라는 것을 알 수 있다. 이 값에 처음에 나는 최대공약수 4를 곱하면 정답이 산출된다.
• 전체로 대입해서 보면 answer = (x/최대공약수 + y/최대공약수 - 1) * 최대공약수이며 다시 계산하면
• answer = x + y - 최대공약수가 된다.

최대공약수 구하기

유클리드 호제법

• 두 개의 자연수 a,b에서 a를 b로 나눈 나머지를 r이라고 가정하면 a,b의 최대공약수는 b,r의 최대공약수와 같다. 이 점을 이용하여 b를 r로 나눈 r1을 구하고 r을 r1으로 나눈 나머지를 구해서 0이 되었을 때 나누는 수가 a,b의 최대공약수이다. 식으로 구현하면 아래와 같다.

function solution(num1, num2) {
    const gcd = (a, b) => a % b === 0 ? b : gcd(b, a % b);
    return gcd(num1, num2);
}