멀쩡한 사각형

🔗 문제 링크

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

❔ 문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다.

이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다.

새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.

가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

⚠️ 제한사항

• W, H : 1억 이하의 자연수

---

💡 풀이 (언어 : Java & Python)

수학적 규칙을 찾아 구현하는 문제였지만 풀이에 실패했다. 이 문제의 규칙성은 가로 w, 세로 h 인 경우 대각선으로 버려지는 사각형의 개수는 (w + h - 1)이고, 전체 사각형의 최대공약수를 구하는데 최대 공약수는 작은 대각선이 그어지는 범위의 사각형들의 개수이고, 전체 사각형은 작은 사각형 (w/최대공약수) (h/최대공약수)들의 모음이다. 작은 사각형 범위에서 지워지는 사각형의 개수 작은 대각선이 그어지는 범위의 사각형들의 개수를 구해서 전체 사각형에서 빼주면 정답이다. 마지막으로 주의할 점은 가로 세로 길이의 범위가 1억이므로 곱하면 int의 범위를 초과하므로 (long)을 붙여서 범위를 키워줘야 한다.

Java

class Solution {
    // 최대 공약수 구하기
    private int gcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
    public long solution(int w, int h) {
        long count = gcd(w, h);
        long all = (long) w * h;
        return all - (w/count + h/count - 1) * count;
    }
}

Python

# 최대 공약수 구하기
def gcd(a, b):
    if b > a:
        a, b = b, a
    while b > 0:
        a, b = b, a % b
    return a

def solution(w,h):
    return (w * h) - (w + h - gcd(w,h))