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

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

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

가로세로가 주어진 직사각형 종이에 대각선이 그어져 있는데, 그어진 조각은 사용할 수 없으므로 멀쩡한 조각만 찾는 알고리즘입니다.

계산 방법이 있는데, 대각선이 지나가는 사각형의 개수는 가로 + 세로 - 최대공약수 입니다.

그러므로 총 사각형의 개수는 총 개수 - 가로 - 세로 + 최대공약수 입니다.

 

다만 수가 1억 이상이다보니, int형을 longlong으로 변환하는 과정에서 오류가 많이 나서 헷갈린 부분이 있었습니다.

long 형에 int * int를 넣는 경우, 두 수를 곱한 다음에 형변환을 하게 되므로 long형으로 계산되도록 형을 지정해 주었습니다.

using namespace std;

long long solution(int w,int h) {
    long long answer = 1;
    long long multi = (long)w*h;  // 총 박스의 개수
    long long sum = w + h;  // 합계
    int div = 2;            // 나누는 변수
    long long count = 1;    // 최대공약수
    if(w == h)
    {
        answer = multi - w; // 같은 경우
        return answer;
    }
    
    while(div <= w && div <= h)
    {
        if(w % div == 0 && h % div == 0)    // 둘다 나눠지는 경우
        {
            w = w/div;
            h = h/div;
            count = count * div;    // 최대공약수를 구함
        }
        else
        {
            div++;
        }
    }
    answer = multi - sum + count;
    
    return answer;
}