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

문제

예제의 그림에서 눈치챌 수 있다시피 직사각형에서 더 긴 쪽을 세로로 둔 다음, 전체 직사각형 개수 - ceil(기울기)*가로의 길이해주면 정답을 얻을 수 있다. 그런데 기울기는 세로/가로이므로 기울기를 구하는 과정에서 오버플로가 발생했다. 연산 순서를 바꿔 계산을 할 수도 있겠지만 방법을 찾아보았다.

놀랍게도 두 변의 길이의 최대공약수를 구하면 된다. w와h를 최대공약수로 나눈 w'와 h'를 가지고 생각해보면, 대각선은 처음 정사각형에서 출발해 도착할 정사각형에 도달할 때 까지 w'-1개의 세로선과 h'-1개의 가로선을 지난다. 그래서 출발 정사각형을 포함해 총 (w' - 1) + (h' - 1) + 1 = w' + h' - 1개의 정사각형을 지난다. 여기에 최대공약수를 곱해주면 총 w + h - gcd(w, h)개의 정사각형을 지난다..!

그리고 입력으로 들어오는 w와 h도 꼭 타입 변환 해주기.. 쒸익…

using namespace std;

long long gcd(long long a, long long b) {
	long long r;
	while (b) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

long long solution(int w, int h) {
	long long W = (long long)w;
	long long H = (long long)h;
	return W * H - (W + H - gcd(W, H));
}