문제
https://programmers.co.kr/learn/courses/30/lessons/62048
풀이
function solution(w,h){
var answer = 1;
var gcd = 1;
var min = Math.min(w,h);
for(var i=min; i>0; i--){
if((w%i===0) && (h%i===0)){
gcd = i;
break;
}
}
answer = w*h - (w+h-gcd);
return answer;
}더 생각해보기
필요 사전지식: 직사각형(정사각형)의 대각선이 지나는 단위사각형의 개수에 관한 알고리즘 (출처)
w×h 사각형에서
w과 h의 최대공약수가 a라고 할 때
w = ab
h = 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 이 된다.
- 대각선이 지나는 단위정사각형'에 대한 문제 중 직사각형의 각 변을 m,n이라고 할때 공식은 m+n-(m과n의 최대공약수). 공식 유도 과정에서 대각선이 지나는 사각형들을 모두 변으로 모으면 'ㄱ'모양이나 'ㄴ'모양으로 되는 것을 이용.
참고사항
직사각형(정사각형)의 대각선이 지나는 단위사각형의 개수에 관한 알고리즘** (출처)
happy