멀쩡한 사각형

---

🔗 🔗 멀쩡한 사각형

문제 설명

---

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.

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

제한사항

---

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

입출력 예

---

입출력 예 설명

---

입출력 예 #1

가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

풀이

---

단서가 없으니 주어진 정보를 통해 패턴을 유추해보자.

특정 지점마다 선분이 정확히 교차하는 곳이 존재하며, 해당 부분을 위 그림에서 파란색 원으로 표시했다.

파란색 원의 좌표값은 (2, 3), (4, 6), (6, 8), (8, 12)이 된다.

즉, (2, 3)부터 정확히 2씩 좌표값이 더해지며, 총 4번의 동일한 패턴이 관측된다.

(8, 12) -> (2, 3)은 각 좌표값을 4로 나누어 얻을 수 있는데, 여기서 4는 w와 h의 값인 8과 12의 최대공약수다.

따라서, w, h, w와 h의 최대공약수를 적절히 계산하면 일반식을 도출할 수 있다.

패턴을 발견했으니, 해당 패턴의 직사각형에서 제외되는 직사각형의 일반식을 구하기만 하면 된다.

패턴이 최대공약수만큼 반복되므로, 일반식을 유추하면 아래와 같다.

사용 가능한 직사각형 수 = 전체 직사각형 수 - (패턴에서 제외되는 직사각형 수 * 최대공약수)

각 패턴별로 분석하면 패턴에서 제외되는 직사각형 수를 쉽게 알 수 있다.

1. (2, 3) 짜리 직사각형. 4개의 직사각형이 영향을 받는다.
2. (5, 2) 짜리 직사각형. 6개의 직사각형이 영향을 받는다.
3. (1, 1) 짜리 직사각형. 1개의 직사각형이 영향을 받는다.

이러한 패턴으로 미루어볼 때, 패턴에서 제외되는 직사각형의 수는 가로 + 세로 - 1이 된다.

따라서 최종적인 일반식은 아래와 같다.

(w * h) - (((w / gcd) + (h / gcd) - 1) * gcd)가 된다.

반환값이 long이므로, int를 반환하지 않도록 주의하자.

코드

---

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 멀쩡한 사각형 클래스
 *
 * @author RWB
 * @since 2021.12.26 Sun 22:31:31
 */
class Solution
{
	/**
	 * 해답 반환 메서드
	 *
	 * @param w: [int] 가로 길이
	 * @param h: [int] 세로 길이
	 *
	 * @return [int] 해답
	 */
	public long solution(int w, int h)
	{
		long ref = gcd(w, h);
		
		return ((long) w * h) - (((w / ref) + (h / ref) - 1) * ref);
	}
	
	/**
	 * 유클리드 호제법 연산결과 반환 메서드
	 *
	 * @param n: [int] 정수 1
	 * @param m: [int] 정수 2
	 *
	 * @return [int] 최대공약수
	 */
	private int gcd(int n, int m)
	{
		while (m != 0)
		{
			int r = n % m;
			
			n = m;
			m = r;
		}
		
		return n;
	}
}