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

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

프로그래머스

기하학과 수학적인 접근이 중요한 문제이다 

입출력 예 그림을 보면 가로는 8개만큼 겹치고 세로는 12개만큼 대각선에서 겹친다 

교차점은 중간에 보면 4개로 최대공약수 만큼 발생한다.

따라서 대각선에서 겹치는 부분에서 중복되는 교차점을 빼주면 되는 것이다.

중요한건 패턴을 찾고 수학적으로 기술하는게 중요할 것 같다.

#include <cmath>
using namespace std;
//대각선은 w개의 가로 격자선과 h개의 세로 격자선을 통과 따라서 W+H개의 경계선을 지나게 된다.
//교차점 최대공약수만큼 발생
//경계선- 중복된 교차점
int getGCD(long long w,long long h){
    int small,big;
    if(w>h){
        big=w;
        small=h;
    }else{
        big=h;
        small=w;
    }
    int mod=big%small;
    while(mod>0){
        big=small;
        small=mod;
        mod=big%small;
    }
    
    return small;
}

long long solution(int w,int h) {
    long long answer;
    long long W=w;
    long long H=h;
    
    int gcd=getGCD(W,H);  
    long long total=W*H;
    answer=total-(W+H-gcd);
    return answer;
}