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

분류 : 구현

 

요구사항

대각선을 그었을때, 대각선에 속하지 않는 사각형의 갯수 구하기

 

풀이

정답 도출식은 w*h - (w+h-gcd)이다

gcd구하는 방법은 유클리드 호제법이 있던데 그냥 구현해 보았따

우리 흔히 하는 방법으로 구했다

안나눠질때 까지 나누어주고 나눈 숫자는 곱해서 gcd를 찾는다

 

#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std;
long long gcd1(long long w, long long h) {
	long long num = 1;
	while (true) {
		long long tempmin = min(w, h);
		long long flag = 0;
		for (int i = 2; i <= tempmin; i++) {
			if (w % i == 0 && h % i == 0) {
				w = w / i;
				h = h / i;
				num = num * i;
				flag = 1;
				break;
			}
		}
		if(flag==0)
			break;

	}
	return num;
}
long long solution(int w, int h)
{
	long long answer = 1;
	long long nw = w;
	long long nh = h;
	long long gcdnum = gcd1(nw, nh);
	answer = (nw * nh) - (nw + nh - gcdnum);
	return answer;
}