코딩테스트 연습 > Summer/Winter Coding(2019) > 멀쩡한 사각형

function solution(w, h) {
    return w*h-(w+h-gcd(w,h));
}

function gcd(n1, n2) {
  return n1%n2 ? gcd(n2, n1%n2) : n2;
}

이건그냥 수학문제다... 최대공약수 구하는 것빼고는

 

w와 h가 공약수가 있으면 문제를 w와 h를 공약수로 나눈 w'과 h'으로 나눌 수 있다.

w'와 h'이 서로소일 때

대각선은 끝 꼭지점에 도달하기전 w'-1개의 세로선과 h'-1개의 가로선을 지나고 지날때마다 새로운 정사각형이 추가 된다. 그래서 첫 정사각형을 포함 1 + (w'-1) + (h'-1) = w' + h' - 1개의 정사각형을 지나게 되고 최대공약수를 다시 곱해주면 w + h - gcd(w,h)