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

출처 

programmers.co.kr/learn/courses/30/lessons/62048

코딩테스트 연습 - 멀쩡한 사각형

문제 설명

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

 

제한 사항

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

입출력 예

 

문제 풀이

아무리 머리를 굴려도 내 머리로는 안되는 것 같아 남의 블로그를 참고 했다. 

일단 위의 예시를 통해 대각선이 지나가는 사각형의 패턴이 반복된다는 것을 눈치채면 생각보다 쉽게 풀린다.

전체는 8x12에서 2x3이 반복된다는 사실을 알 수 있다.

W, H의 최대 공약수를 g라고 하면 (W/g) x (H/g)와 W x H는 같은 패턴의 대각선을 그리며 지나간다

그러므로 (W/g) x (H/g)에서 대각선이 지나가는 갯수를 구해 g만큼 곱해주면 된다. 

그럼 (W/g) x (H/g)에서 대각선이 지나가는 사각형의 갯수는 어떻게 구할까?

이는 생각보다 간단하다(나는 이 부분을 생각하지 못했다)

 

사각형의 대각선은 무조건 w + h(가로, 세로를 다 지나므로)만큼을 지나게 된다. 그리고 세로와 가로의 출발점이 중복되기 때문에 여기서 1을 빼준 w+h-1이 대각선이 지나가는 사각형의 갯수가 된다. 

따라서 지나가는 사각형의 개수는 ((W/g) + (H/g) - 1) * g가 되고 정답은 전체 사각형 갯수에서 이를 빼주면 된다.

int Gcd(int a, int b) {
	int minval = a < b ? a : b;
	int ret = 1;
	while (0 < minval) {
		if (a%minval == 0 && b%minval == 0) {
			return minval;
		}
		minval--;
	}
	return ret;
}
long long solution(int w, int h) {
	int gcd = Gcd(w, h);
	long long sum = (long long)w * (long long)h;
	return sum - (gcd)*((h/gcd) + (w/gcd) -1);
	
}