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

문제

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

 

---

 

문제 개요

주어진 문제는 가로 길이 W와 세로 길이 H인 직사각형 종이가 대각선으로 잘려, 두 개의 직각삼각형으로 나뉜 상태에서 시작합니다. 이 종이에서 1cm × 1cm 크기의 정사각형으로 잘라낼 수 있는 최대 개수를 구하는 것입니다. 대각선에 의해 사용 불가능한 정사각형들을 제외한 나머지 정사각형의 수를 계산하는 문제입니다.

 

접근 방법

1. 대각선이 지나가는 칸의 수는 직사각형의 가로(W)와 세로(H)를 고려하여 계산됩니다.
2. 대각선이 지나가는 격자 칸의 총 개수는, 다음과 같은 성질을 기반으로 계산됩니다

W+H−gcd(W,H)

 

왜 이렇게 계산할까?

1. 대각선의 경로

• 직사각형의 한 모서리에서 반대 모서리까지 대각선을 그리면, 이 대각선은 여러 개의 1 x 1 격자칸을 가로지르게 됩니다.

2. 가로선과 세로선

• 대각선이 가로선을 만날 때마다 새로운 격자칸으로 들어가고, 세로선을 만날 때마다 또 다른 격자칸으로 들어갑니다.
• 예를 들어, 대각선이 (0,0)에서 (W,H)로 이동할 때, 대각선이 가로선과 세로선을 만나는 지점에서 격자칸이 바뀌게 됩니다.

3. 중복 세기 문제

• 대각선이 특정 격자칸의 모서리를 지나갈 때, 그 격자칸은 가로선과 세로선 모두를 동시에 지나가게 됩니다. 이 경우, 해당 격자칸이 두 번 세어질 수 있습니다.
• 예를 들어, 대각선이 (1,1)에서 (2,2)로 이동할 때, (1,1)과 (2,2) 두 격자칸의 모서리를 지나가게 되므로, 이 두 격자칸이 각각 가로선과 세로선을 만나는 지점에서 중복으로 세어질 수 있습니다.

4. 최대공약수(gcd)의 역할

• gcd(W, H) 는 대각선이 지나가는 격자칸의 모서리의 수를 나타냅니다.
• 즉, 대각선이 ( W )와 ( H )의 최대공약수에 해당하는 지점에서 격자칸의 모서리를 지나갈 때, 그 지점에서 두 격자칸이 동시에 세어지는 것을 방지하기 위해 이 값을 빼줍니다.
• 예를 들어 W=8, H=12라면 8:12는 2:3의 비율과 같습니다.
• 2:3 비율로 W인 8과 H인 12의 최대공약수 gcd (W,H) = 4만큼 반복적으로 동일한 패턴이 나타납니다.
• 새로운 패턴으로 진입할 때 두 격자칸의 모서리를 지나가게 되므로 최대공약수만큼 빼주면 됩니다.

 

코드

class Solution {
    public long solution(int w, int h) {
        long gcd = gcd(w, h);  // 최대공약수 계산
        return ((long) w * h) - (w + h - gcd);  // 전체 격자에서 대각선이 지나는 격자칸 제외
    }

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