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

문제 : 멀쩡한 사각형

 

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

 

 분석

 직사각형 구조이기에 대각선 기준으로 대칭인 것을 생각하자.

 

8 x 12

저 한 블록의 규칙을 정리하자면 다음과 같다.

 

블록의 크기는 (w / gcd) x (h / gcd) 이다. (gcd는 주어진 수의 최대 공약수이다.)

블록 내의 유호 하지 않은 정사각형의 개수는 (블록의 가로 + 블록의 세로 -1)이다.

 

 구현

※ gcd를 구하는 과정을 재귀로 처리했다.

// GCD func, x > y 가정
int calGCD(int x, int y)
{
	if (y == 0) return x;
	else return calGCD(y, x%y);
}

long long solution(int w, int h) {
	long long answer = 1;
	long long ret = (long long)w*(long long)h;

	int gcd = calGCD(max(w, h), min(w, h));

	return answer = ret - gcd * (w / gcd + h / gcd - 1);
}