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

프로그래머스

 

W = 8, H = 12

• 잘려나간 종이들은 동일한 패턴을 가짐
• 패턴은 W와 H의 최대공약수만큼 존재
• W를 최대공약수로 나눈 값을 X, H를 최대공약수로 나눈 값을 Y라 할 때 각 패턴에서 사용할 수 없게 되는 정사각형의 개수는 X + Y - 1

> 사용할 수 있는 정사각형의 개수는 (W x Y) - (gcd x (X + Y - 1)) = (W x Y) - (W + Y - gcd)

> 여기서 입력되는 W, H는 1억 이하의 자연수기 때문에 W와 Y를 long 타입으로 캐스팅해주어야함

 

#include <iostream>

using namespace std;

int gcd(long long a, long long b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

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