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

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

using namespace std;

long long gcd(long long a, long long b){
    while (b != 0){
        long long temp = b;
        b = a % b;
        a = temp;
    }
    
    return a;
}

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

---

📝 풀이

대각선이 직사각형을 통과할 때, 가로선 또는 세로선과 교차할 때마다 새로운 격자칸에 들어갑니다.

따라서 w + h의 수가 대각선이 지나는 격자칸의 총 수라고 할 수 있습니다.

그러나, 주의 할 점은 대각선이 지나갈 때 가로선과 세로선을 동시에 교차하는 경우도 있다는 것입니다.

가로와 세로가 만나는 지점은 최대공약수(GCD)만큼 존재하게 됩니다.

최종적으로 대각선이 지나는 격자칸의 총 수를 구하는 공식은 w + h - gcd(w, h) 입니다.

 

요구 사항은 사용할 수 있는 정사각형의 개수를 구하는 것이니 최종 공식은 w * h - (w + h - gcd(w,h) 입니다.

이 공식을 풀어 w * h - w - h + gcd(w,h)로 변환하였고,

w와 h의 곱셈은 오버플로우가 발생할 수 있어 long long으로 형변환을 해줍니다.