프로그래머스 | Level 2 | 멀쩡한 사각형
Programmers | Level 2 | 멀쩡한 사각형
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Math
Description
가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.
Constraints
- W, H : 1억 이하의 자연수
Examples
| W | H | result |
|---|---|---|
| 8 | 12 | 80 |
Solutions
Code
import java.util.*;
class Solution {
public long solution(int w, int h) {
long total = (long) w * h; // 전체 정사각형의 개수
long unusable = w + h - gcd(w, h); // 사용할 수 없는 정사각형의 개수
return total - unusable; // 전체 개수에서 사용할 수 없는 개수를 뺀 값이 정답
}
// 두 수의 최대공약수를 구하는 함수 (유클리드 호제법 사용)
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a; // GCD 반환
}
}
Approaches
이 문제는 기하학적 특성을 활용하여, 직사각형에서 대각선이 지나가며 사용할 수 없게 되는 정사각형의 수를 계산하는 수학적 문제입니다.
1. 문제 분석
가로 길이가 W이고 세로 길이가 H인 직사각형에서 대각선을 그었을 때, 잘라지면서 사용할 수 없게 되는 정사각형의 개수를 정확하게 계산해야 합니다. 대각선이 직사각형을 지나갈 때, 여러 개의 정사각형을 관통하면서 지나가게 되는데, 이 과정에서 대각선이 지나가는 정사각형의 수는 W와 H의 크기와 비율에 따라 달라집니다.
대각선이 어떤 정사각형의 내부를 지나가면, 새로운 정사각형이 만들어져 사용할 수 없게 됩니다. 반면, 대각선이 정사각형의 꼭짓점을 통과할 때는 그 지점에서는 두 개의 정사각형이 함께 잘리므로, 잘라지는 정사각형의 개수가 줄어들게 됩니다. 이러한 교차점의 개수는 W와 H의 최대공약수(GCD)에 의해 결정됩니다. 즉, 대각선이 격자 모서리를 정확히 지나가는 위치는 최대공약수 값 만큼 발생하게 되며, 이러한 지점에서는 새로운 정사각형이 생성되지 않기 때문에 해당 횟수만큼 잘라지는 정사각형의 개수에서 제외해야 합니다.
결론적으로, 대각선이 지나가면서 잘라지는 총 정사각형의 수는 W + H - GCD(W, H)로 계산할 수 있으며, 전체 정사각형의 개수에서 이를 빼면 사용할 수 있는 정사각형의 개수를 구할 수 있습니다.
2. 접근 방식
이 문제의 핵심은 대각선이 지나가는 격자칸의 개수를 수학적으로 계산하는 것입니다. 이를 위해 최대공약수(GCD)를 사용하여 반복되는 패턴을 찾고, 그에 따라 잘라지는 정사각형의 개수를 계산할 수 있습니다.
- 최대공약수(GCD) 계산: 두 수
W와H의 최대공약수를 구하는 것은 반복되는 패턴을 찾는 데 중요합니다. GCD는 대각선이 격자칸을 몇 번 지나가면서 잘리는지에 대한 정보를 제공합니다. - 잘라지는 정사각형의 개수 계산: 전체 가로와 세로 길이를 더한 후 최대공약수를 빼면, 대각선이 지나가면서 실제로 잘리는 정사각형의 개수를 구할 수 있습니다. 이는
W + H - gcd(W, H)로 계산됩니다. - 전체 정사각형에서 잘린 부분 제외: 전체 직사각형의 정사각형 개수에서 잘라지는 정사각형의 개수를 뺀 값이 사용할 수 있는 정사각형의 개수가 됩니다.
3. 전체 정사각형 개수 계산
먼저, 주어진 직사각형의 전체 정사각형 개수를 구합니다. 이때, W와 H가 매우 큰 값일 수 있으므로, long 타입을 사용하여 정수 오버플로우를 방지해야 합니다. 전체 개수는 W와 H의 곱으로 구할 수 있습니다.
long total = (long) w * h; // 전체 정사각형의 개수
4. 사용할 수 없는 정사각형의 개수 계산
대각선이 지나가는 경로에 있는 정사각형의 개수는 W + H - gcd(W, H)로 계산할 수 있습니다. 여기서 gcd(W, H)는 대각선이 격자선을 통과하며 잘라지는 교차점의 수를 나타냅니다. 만약 W와 H가 서로소(최대공약수가 1)라면, 대각선이 모든 격자선을 통과하며 잘라지므로 W + H - 1개의 정사각형이 잘라지게 됩니다. 반면, W와 H의 최대공약수가 크면 대각선이 몇 개의 격자선을 한 번에 통과하게 되어, 새로운 정사각형이 생성되지 않고 중복된 잘림이 발생합니다.
이를 계산하기 위해 유클리드 호제법을 사용하여 두 수의 최대공약수를 효율적으로 구할 수 있습니다. 유클리드 호제법은 두 수의 나머지를 반복적으로 구하여 최대공약수를 찾는 알고리즘입니다. 다음 gcd 함수는 유클리드 호제법을 이용하여 두 수 a와 b의 최대공약수를 계산합니다.
// 두 수의 최대공약수를 구하는 함수 (유클리드 호제법 사용)
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a; // GCD 반환
}
이렇게 계산한 gcd 값은 대각선이 교차하는 주요 지점을 나타내므로, W + H - gcd(W, H)를 통해 정확하게 사용할 수 없는 정사각형의 개수를 구할 수 있습니다.
long unusable = w + h - gcd(w, h); // 사용할 수 없는 정사각형의 개수
위 식은 대각선이 잘라지는 정사각형의 개수를 정확하게 계산하여 저장합니다. 최종적으로 전체 정사각형의 개수에서 이 값을 빼면 사용할 수 있는 정사각형의 개수를 구할 수 있습니다.
5. 최종 결과 도출
전체 직사각형의 정사각형 개수에서 잘라지는 부분을 제외하면, 실제 사용할 수 있는 정사각형의 개수를 구할 수 있습니다. 이 값이 최종적으로 반환할 정답입니다.
// 전체 개수에서 사용할 수 없는 개수를 뺀 값 계산 후 반환
return total - unusable;
전체에서 잘라지는 부분을 뺀 값이 최종적으로 사용할 수 있는 정사각형의 개수가 됩니다.
Complexity
- ⏳ TC: O(log(min(W, H)))
- 💾 SC: O(1)
유클리드 호제법을 사용하여 W와 H의 최대공약수를 계산하는 데 걸리는 시간은 O(log(min(W, H)))입니다. 전체 계산은 최대공약수 계산 이후 간단한 산술 연산만 수행하므로, 최종 시간 복잡도는 O(log(min(W, H)))입니다. 추가적인 메모리 사용이 없으므로 공간 복잡도는 O(1)입니다.
- Algorithm
- Math