[Programmers] Lv2.멀쩡한 사각형

• 이 문제는 C++로 풀이를 작성하였습니다.

문제

예제

---

풀이

	#include <cmath>
	using namespace std;
	// 최소공배수 구하기
	int gcd(int w,int h){
	int g;
	while(w%h!=0){
	int r=w%h;
	w=h;
	h=r;
	}
	g=h;
	return g;
	}
	// 풀이 원리
	// 1. 최소공배수로 나누어서 가로, 세로를 서로소가 되게끔 만듭니다.
	// 2. 대각선을 통해서 상단왼쪽 끝과 하단오른쪽 끝이 만납니다.
	// 3. 여기서 대각선은 무조건 모든 가로에 해당하는 좌표를 한번씩 지납니다.
	// 4. 마찬가지로 세로에 해당하는 좌표로 한번씩 지납니다.
	// 5. 가로와 세로가 두번 겹치는게 1개 존재합니다.
	// 5. 따라서 대각선이 지나가서 빠지는 숫자는 (w+h-1) , w와 h는 서로소
	long long solution(int w,int h)
	{
	// long long형으로 형 변환 꼭 필요!
	long long answer = (long long)w*h;
	// 최소공배수 찾기
	int g=gcd(w,h);
	// 서로소 만들기
	w/=g;
	h/=g;
	return answer-g*(w+h-1);
	}

view raw Programmers Lv2.normal square.cpp hosted with ❤ by GitHub

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.