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

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

 

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

프로그래머스

---

 

해결전략

 

기하학, 수학

그리디 알고리즘 Greedy Algorithm

 

 

 

핵심 아이디어

w x h 크기의 사각형이 있다. 사각형을 대각선으로 자를 때 영향을 받는 블록은 " w + h - 1 " 만큼의 블록이다.

 

w x h 크기의 사각형을 대각선으로 자를 때, 반드시 가로는 w 만큼, 세로는 h 만큼 가야한다.

 

가로 w, 세로 h만큼 총 w + h을 가게 되는데, 가로로 이동할 때와 세로로 이동할 때 시작점은 같기 때문에  -1 을 하여 중복을 제거해준다.

 

 

( a + b - 1 ) * ( h / b )

 

•  (w 비율 + h 비율 - 1) * ( h / h 비율 )  
•  위의 서술한 규칙성을 적용하면   (w 비율 + h 비율 - 1) 이다.
•  (w 비율 + h 비율 - 1)에 (h / h 비율) 만큼 반복되니 곱해준다.

---

 

정답코드

 

#include <iostream>
using namespace std;

long long GCD(long long x, long long y) // 최대공약수를 구하는 함수
{
	return y ? GCD(y, x % y) : x;
}

long long solution(int w, int h) {

	if (w > h) swap(w, h); // w h보다 크다면 두 수를 교환

	long long gcd = GCD(w, h); // w와 h의 최대공약수를 구함

	// w와 h를 최대공약수로 나눈 값을 저장
	long long a = w / gcd;
	long long b = h / gcd;

	// 전체 사각형 개수를 계산
	long long answer = (long long)w * (long long)h;
	
    if(a == 1){
		// a비율이 1인 경우, b비율 방향 길이만큼의 사각형이 대각선에 의해 없어짐
		answer -= b * w;
	}
	else{
		// 그렇지 않은 경우, (a + b - 1) * (높이 / b)만큼의 사각형이 대각선에 의해 없어짐
		answer -= (a + b - 1) * (h / b);
	}

    return answer;
}

int main(){
	cout << solution(12, 12) << "\n"; // 144 - 12 = 132
	cout << solution(4, 12) << "\n"; // 48 - 12 = 36
	cout << solution(8, 12) << "\n"; // 96 - 16 = 80
	cout << solution(10, 12) << "\n"; // 120 - 20 = 100
	cout << solution(7, 11) << "\n"; // 77 - 17 = 60
}

 

---

 

 

실수한 부분

 

매개변수로 들어오는 w와 h의 자료형은 int다.

int * int 할 때 int 범위 벗어날 수 있기 때문에 long long으로 캐스팅 해줘야 한다.

 

변경 전 

long long answer = w * h;

 

변경 후

long long answer = (long long)w * (long long)h;

 

 

이 작업을 수행하지 않으면 테스트 12~17번이 틀렸다고 나온다.

---