프로그래머스 멀쩡한 사각형

문제 설명

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

제한사항

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

입출력 예

WHresult

8

12

80

입출력 예 설명

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

 

 

---

class Solution {
	public long solution(int w,int h) {
		long answer = 1;
		long gcd = 0;
		long total = (long)w * (long)h;
		
		if(w == h) answer = total - w;
		
		// 최대공약수를 구하기 위한 for문
		gcd = getGcd(w, h);
		answer = total - gcd * ((w / gcd) + (h / gcd) - 1);
		return answer;
	}

	public static long getGcd(int w, int h) {
		long result = 0;
		if(h == 0) {
			return w;
		}
		return getGcd(h, w % h);
	}
}

 

코드 설명:

직접 해결하지 못하여 다른 사람들의 풀이를 참고하였다.

우선 접근방법은 전체 사각형 개수에서 잘라진 사각형의 개수를 빼어 정답을 return 해준다.

 

우선 solution메서드로 전달되는 w,h 인자들을 long타입으로 캐스팅하여 전체 사각형 개수를 구해준다 ( long total )

만약 w, h가 같다면, 즉, 정사각형이라면 전체 개수에서 한 변의 길이만큼만 빼주고 리턴해주고 프로그램을 종료하면 된다.

 

그렇지 않다면 규칙을 찾아야한다. 이 문제의 주어진 예제 그림을 보고 어느 정도 일정한 규칙이 반복될 것이라고 생각을 하긴 했다. 하지만 풀어내지 못하여 다른 코드를 참고를 했고 주어진 두 w, h의 최대공약수를 이용하여 풀어나가는 것을 알 수 있었다.

 

위의 예제 그림은  w = 8, h = 12 의 직사각형을 대각선으로 자른 형태다. 대각선이 지나가는 사각형들을 보면 일정한 모양의 패턴을 띄면서 지나가고 있다. 두 수의 최대공약수를 구한다. 

(나는 따로 getGcd라는 최대공약수를 구하는 재귀함수를 구현하여 두 수의 최대공약수를 리턴해주도록 했다.) 

8, 12의 최대공약수는 4가 나온다. 

 

문제는 어째서 두 수의 최대공약수를 구해서 풀어나가야 하냐는 것이다.

 

그 이유는 다음과 같다.

 

이 문제에서 최대공약수를 구하는 이유는 대각선이 지나가는 규칙적인 사각형을 보면 (w / gcd) x (h / gcd) 크기의 사각형이 gcd만큼 반복되고 있기 때문인 것이다.

 

8 X 12 직사각형

 

 

대각선을 따라 2 x 3크기의 총 4개의 직사각형 위를 지나는 것을 알 수 있고 그 안에서도 실제로 잘려나간 사각형은

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

 

결과적으로 전체 사각형의 개수 96개 중 대각선이 지나가는 사각형의 개수 16개를 뺀 80개의 사각형이 정답이 된다.

 

 

다른 크기의 예제로 검증을 해봐도 풀이는 적용이 된다.

6 X 9 직사각형

 

6과 9의 최대공약수는 3이 되고 (w / gcd) X (h / gcd)크기의 사각형을 gcd(3번)만큼 지나가고 있다. 그리고 빨간 사각형에서 실제로 대각선이 지나가는 사각형의 개수는 (w / gcd) + (h / gcd) - 1개 = 4개가 된다.

 

answer = total - gcd * ((w / gcd) + (h / gcd) - 1);

54 - 12 = 42..