[62048] 멀쩡한 사각형

✔ 멀쩡한 사각형

[프로그래머스 62048]

문제 분석하기

선분이 정확하게 교차하고 있는 곳은 W와 H의 최대공약수만큼 반복되므로 이를 이용해 일반식을 유추하도록 함

사용 가능한 직사각형의 수 = 전체 직사각형의 수 - (반복되어 제외되는 직사각형의 수 * 최대공약수 gcd)

이때 반복되어 제어되는 직사각형의 수는 W가 H보다 길 때, W가 H보다 짧을 때, W가 H와 같을 때가 있으므로

이 세 경우의 수를 분석하면 반복되어 제어되는 직사각형의 수는 W/gcd + H/gcd - 1

 

예) W = 8, H = 12

W와 H의 최대공약수는 4이므로 4개짜리 모양의 패턴이 4번 반복됨

그러므로 사용 가능한 직사각형의 수 = 96 - (8/4 + 12/4 - 1) * 4 = 96 - 4 * 4 = 80

(8, 12) → (2, 3), (4, 6), (6, 8), (8, 12)

손으로 풀어보기

1. W와 H의 최대공약수 gcd(W, H)를 구함
2. W * H - (W/gcd(W, H) + H/gcd(W, H) - 1) * gcd(W, H)를 반환

슈도코드 작성하기

w, h(직사각형 종이의 가로 길이와 세로 길이)
wh = 최대공약수 함수(w, h)
w * h - (w/wh + h/wh - 1) * wh 반환

최대 공약수 함수 {
    a(w과 h 중 큰 수)
    b(w과 h 중 작은 수)
    if(b가 0이라면)
        a가 최대 공약수
    else
        최대 공약수 함수(작은 수, 큰 수 % 작은 수)
}

코드 구현하기

/**
 * 62048) 멀쩡한_사각형
 */
public class L056_62048 {
    // w, h(직사각형 종이의 가로 길이와 세로 길이)
    public long solution(int w, int h) {
        // wh = 최대공약수 함수(w, h)
        long wh = gcd(w, h);
        // w * h - (w/wh + h/wh - 1) * wh 반환
        return (long) w * h - (w / wh + h / wh - 1) * wh;
    }

    // 최대 공약수 함수
    private int gcd(int w, int h) {
        // a(w과 h 중 큰 수)
        int a = Math.max(w, h);
        // b(w과 h 중 작은 수)
        int b = Math.min(w, h);
        // b가 0이라면
        if (b == 0)
            // a가 최대 공약수
            return a;
        else
            // 최대 공약수 함수(작은 수, 큰 수 % 작은 수)
            return gcd(b, a % b);
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L056_62048 solution = new L056_62048();

        int w = 8;
        int h = 12;

        long result = solution.solution(w, h);

        System.out.println(result);
    }
}