[프로그래머스] 멀쩡한 사각형 Summer/Winter Coding(2019)

코딩테스트 연습 - 멀쩡한 사각형

위와 같이 사각형을 대각선 기준으로 반 접었을 때 점선이 겹치는 부분을 제외한 1X1 사각형들의 개수를 구하는 문제이다.

규칙을 찾기 위해

가로가 W, 세로가 H로 W <= H 일 때를 가정하고

W가 1일때부터 값을 늘려가며 몇 번 그려보니

​

W 겹치는 부분

1 H

2 H+1

3 H+2

4 H+3

5 H+4

... ...

​

이런 규칙성을 보였다. 단, 이때 전제조건은 최대공약수가 1인 경우이다.

W와 H의 최대공약수가 2 이상인 경우엔

​

W 겹치는 부분

1 H*GCD

2 (H+1)*GCD

3 (H+2)*GCD

4 (H+3)*GCD

5 (H+4)*GCD

... ...

​

이런 식으로 값에 최대공약수를 곱해줘야 한다.

효율적이게 GCD를 구하기 위해선 유클리드 호제법 알고리즘을 이용해야 하는데

유클리드 호제법은 자연수 a, b (a>b)에 대해 a%b를 r이라 한다면

a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 개념이다

​

예를 들어 20과 12의 최대공약수를 구하려면

20%12는 8이므로 다시 12와 8의 최대공약수를 구해야 한다.

12%8은 4이므로 다시 8과 4의 최대공약수를 구해야 한다.

8%4는 0이므로 8과 4의 최대공약수, 즉 20과 12의 최대공약수는 4가 된다.

​

이 개념을 이용해 재귀로 gcd함수를 만들고 앞서 발견한 규칙으로 answer를 찾으면 끝

#include <iostream>
using namespace std;

long long gcd(int a, int b) {
	if (a % b == 0)return b;
	else return gcd(b, a%b);
}

long long solution(int W, int H) {
	long long answer = 1;
	long long GCD = 1;

	if (W > H)GCD = gcd(W, H);
	else GCD = gcd(H, W);

	long long w = (long long)W / GCD, h = (long long)H / GCD;
	long long sum = (long long)W*(long long)H;

	answer = sum - ((h + w - 1)*GCD);
	return answer;
}