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

최대공약수 접근법:

대각선은 가로선을 W-1 번, 세로선을 H- 1 번을 지나며 총 W + H - 1 개의 사각형을 망가뜨립니다.
이때 최대 공약수 G 가 존재한다면 사각형을 작은 사각형인 W/G 와 H/G인 사각형 G개로 나눌수 있습니다.
각 작은 사각형 안에서 망가지는 개수는 W/G + H/G - 1 개 입니다.
총 망가지는 개수는 W + H - G 개 입니다.

#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;

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

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

기울기 접근법:

대각선은 항상 0,0 에서부터 W,H 까지 지나간다는 것을 생각한 방법
대각선 아래에있는 멀쩡한 사각형의 갯수를 구한 다음, 이를 누적 한다.
총 사각형의 갯수는 대각선의 위와 아래 니깐 2배를 곱한다.

#include <iostream>

using namespace std;

long long solution(int w, int h) {
    long long answer = 0;
    
    // x를 1부터 w-1까지 돌면서 대각선 아래의 멀쩡한 사각형 개수를 구함
    for (int x = 1; x < w; ++x) {
        // y = (H * x) / W
        // 자료형 오버플로우를 막기 위해 명시적으로 (long long) 캐스팅
        long long y = ((long long)h * x) / w;
        
        // y값이 곧 해당 열의 온전한 사각형 개수 (C++ 정수 나눗셈은 자동으로 내림 처리됨)
        answer += y;
    }
    
    // 대각선 아래의 사각형만 구했으므로, 위쪽 영역까지 포함하기 위해 곱하기 2
    return answer * 2;
}

문자열 압축[프로그래머스]