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

문제 링크

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

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

 

풀이

가로, 세로가 주어지고 격자점을 관통하는 직선이 보입니다. 이건 누가 봐도 소인수 관련 문제입니다.

최대 공약수로 몇 번 끄적여서 규칙을 찾았습니다.

 

정답 코드

const gcd = (a, b) => b===0 ? a : gcd(b, a%b);
function solution(w, h) {
	const g = gcd(w, h);
	const ans = w*h - g*(w/g+h/g-1);
	
	return ans;
}