멀쩡한 사각형(level2)

링크

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

문제

사각형의 꼭지점을 잇는 선을 그었다. 이런 사각형을 1 x 1 크기로 나누었을 때 선이 닿지 않은 1 x 1 크기의 사각형 개수를 구하라.

예제로 이해

가로가 8, 세로가 12인 사각형을 1 x 1 크기의 사각형으로 나누었을 때, 총 96개의 사각형이 나온다. 여기서 꼭지점을 잇는 선을 그렸을 때 선이 닿는 부분과 닿지 않는 부분은 다음과 같다

이 문제는 공식이 존재하는데 아무것도 긋지 않은 사각형의 개수를 세기 위해서 다음과 같은 식을 계산하면 된다.
원하는 사각형 갯수 = 전체 사각형 갯수 - (가로 + 세로 - 최대공약수)
따라서 8과 12의 최대 공약수는 4이므로 96 - (8 + 12 - 4) = 80이 된다.

코드

function solution(w, h) {
    let num = 0
    
    for(let i = 1; i <= Math.min(w, h); i++) {
        if(w % i === 0 && h % i === 0) {
            num = i
        }
    }
    
    return w * h - ( w + h - num )
}

코드 풀이

for(let i = 1; i <= Math.min(w, h); i++) {
	if(w % i === 0 && h % i === 0) {
		num = i
	}
}

두 숫자의 최대공약수를 구하는 반복문이다. 반복 횟수는 두 숫자 중 작은 숫자 만큼 반복이 들어가며 숫자를 1씩 증가시켜 두 숫자를 나누었을 때 나머지가 두 수 모두 0이라면 그 수를 저장해준다.

반복이 끝나면 두 수를 나누었을 때 나누어 떨어지는 수 중에서 가장 큰 수인 최대공약수를 구할 수 있다.

최대공약수를 구한뒤에 다음 공식에 따라서 계산한 값을 return 해준다.
원하는 사각형 갯수 = 전체 사각형 갯수 - (가로 + 세로 - 최대공약수)