[Algorithm] 프로그래머스 멀쩡한 사각형 - C++, GCD

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

using namespace std;

long long gcd(long long x, long long y){
    long long temp;
    while(y){
        temp = x%y;
        x = y;
        y = temp;
    }
    return x;
}

long long solution(int w,int h) {
    long long answer = 0;
    long long totalSquare = static_cast<long long>(w) * static_cast<long long>(h);

    long long commonDigit = gcd(w, h);

    long long wrongSquare = w + h - commonDigit;

    return answer = totalSquare - wrongSquare;
}

---

 일단 문제를 보고 나서 '기울기를 통해서 뭔가를 할 수 있지 않을까?' 했다가 실패하고 살짝 힌트를 봤던 문제입니다. 일단 힘트는 최대공약수를 사용해라! 였고 이를 통해서 풀 수 있었습니다.

 일단 최대공약수 힌트로 얻을 수 있는건 '최대 공약수 만큼 같은 패턴이 반복된다' 였습니다. 그러면 일단 최대공약수*(패턴 안에서 못쓰는 사각형 수)  식을 세울 수 있고 패턴을 보면 주어진 가로, 세로 길이만큼 사각형이 줄어든다 였습니다.

 

 문제에서 그림을 가져와서 생각해보면 2*3인 사각형에서는 가로에서 2만큼, 세로에서 3만큼 없어지게 되며 처음에 겹치는게 하나씩 있다! 란 사실을 알 수 있습니다. 이를 통해서 w + h - 1의 식을 세울 수 있는데 일단 여기서의 w, h 를 구할 수 있어야 합니다. 

 그건 '같은 패턴이 gcd 만큼 반복된다!' 에서 구할 수 있으며 주어지는 입력값 w, h 를 gcd로 나눠주면 얻을 수 있습니다. 

 그럼 이런 식이 만들어지게 되고 분배법칙을 위해서 위와 같은 코드를 얻을 수 있습니다.

 

- 여기서 C++의 경우 solution에서 캐스팅을 하고 처리를 해야 남은 1/3 테케가 통과됩니다!