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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/62048

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

1. 주의할 점

- 최대공약수로 접근한다

- 직선이 정사각형의 변에 걸친 경우를 고려한다

- Long Long과 Double을 이용하여 연산이 변수의 최대값을 벗어나지 않도록 한다

 

2. 구현

- GCD() 함수를 통해 W와 H의 최대공약수를 구한다

- W와 H를 최대공약수로 나눈다

- Cal() 함수를 통해 바뀐 W x H 직사각형에서 사용할 수 없는 정사각형의 수를 구한다

- 기울기가 소수점일 수 있으므로 Double 타입을 사용하고 과 Floor을 이용하여 왼쪽변의 Y값보다 크지 않은 정수 중에서 가장 큰 정수를 구한다

- Ceil을 이용하여 오른쪽변의 Y값보다 작지 않은 정수중에 가장 작은 정수를 구한다

- Result에 Ceil(우변 Y값)-Floor(좌변 Y값) 값을 계속해서 더한다

 

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

int gcd(int a, int b){
    int n;
    while(b!=0){
        n = a%b;
        a=b;
        b=n;
    }
    return a;
}

long long cal(int a, int b){
    long long result=0;
    double left = 0.0f;
    for(int i=0;i<b;i++){
        double right = (double)a*(i+1)/b;
        result += (ceil(right)-floor(left));
        left = right;
    }
    return result;
}

long long solution(int w,int h) {
    long long answer = (long long)w*h;
    int g = gcd(w,h);
    w/=g;
    h/=g;
    long long cantUse = cal(w,h);
    return answer - cantUse*g;
}