[프로그래머스] 레벨 2 - 멀쩡한 사각형

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

코딩테스트 연습 - 멀쩡한 사각형 | 프로그래머스

레벨 2의 문제다.

생성되는 직사각형의 개수는 gcd만큼이고, 한 직사각형 내 생성되는 하얀 네모는 (w/gcd) + (h/gcd)-1개이다.

따라서, 전체 네모의 개수 sum 에서 gcd개 만큼 (w/gcd)+(h/gcd)-1개를 곱한것을 빼주면 된다.

자료형에 유의해야 한다.

 

 
using namespace std;
 
long long solution(int w,int h)
{
    long long answer;
    int gcd;
    long long sum = (long long)w * (long long)h;
    for(int i = ( w > h ) ? h : w; i > 0; i--){
        if(w % i == 0 && h % i == 0){
            gcd = i;
            break;
        }
    }
    answer = sum - gcd * ((w/gcd)+(h/gcd)-1);
    return answer;
}