[프로그래머스 2레벨] 멀쩡한 사각형 (C++)

using namespace std;
#include <numeric>

long long solution(int w,int h) {
    long long answer = 1;
    
    answer =  (long long)w*h - (w+h) + gcd(w, h);
    
    return answer;
}

 

문제의 예제 기준 그림을 보면 잘려진 패턴이 4개 반복된다.

이는 예제의 W(8), H(12)의 최대공약수 값이다.

따라서 각 잘려진 패턴의 가로 세로 길이 또한 W/최대공약수, H/최대공약수를 한 (2, 3)이다.

 

해당 (2, 3) 형태의 직사각형에서 잘려나간 정사각형을 살펴보면 (2+3)-1의 형태인 것을 알 수 있다.

근데 해당 패턴이 4개 즉, W와 H의 최대공약수 만큼 반복되기에 일단 아래의 식을 얻을 수 있다.

 

이를 다시 정리하여 표현하면 아래와 같다.

 

따라서 최종 답 자체는 간단한 한줄 공식이다.

다만 w, h 값이 int 형인데 w*h의 값은 long long 범위이므로 자료형에 주의해야할 필요가 있다.