[백준 21870] 시철이가 사랑한 GCD (C++)

문제

---

Q1. 사막에서 바늘을 찾는 방법은?

A1. 대학원생을 시킨다.

Q2. 신촌에서 자취방을 구하는 방법은?

A2. 대학원생을 시킨다.

연희동 최고의 대학원생 시철이는 오늘도 바쁘다. 그런 시철이도 이번 주말만큼은 꼭 해야 하는 일이 있었는데, 바로 자취방을 구하는 일이다!

시철이는 신촌에서 가장 아름다운 자취방을 구하고 싶다. 하지만 시철이는 매우 바빴기 때문에 직접 방을 찾아다닐 수 없었다. 그래서 시철이는 인터넷에서 본 매물번호와 GCD(Greatest Common Divisor, 최대공약수)를 이용해 자취방의 아름다움을 예측하려 했다. 아름다움을 측정하는 자세한 방법은 다음과 같다.

1. 매물번호를 나타내는 정수 배열 S가 있다. (|S|=N, |S|는 S의 원소의 개수)
2. 배열 S의 원소를 왼쪽부터 ⌊|S|2⌋$\lfloor \frac{|S|}{2} \rfloor$개 선택하거나, 오른쪽부터 ⌈|S|2⌉$\lceil \frac{|S|}{2} \rceil$개 선택한다. 만약 S의 원소가 단 한 개라면 그 원소를 선택한다.
3. 선택한 원소들의 GCD를 구한다.
4. 선택하지 않은 원소의 배열 S′을 다시 2번부터 반복한다. 
5. 이때, 자취방의 아름다움은 3번에서 구한 GCD의 합의 최댓값으로 정의한다.

교수님의 과제로 쉴 날 없는 시철이는, 그나마 더 나은 삶을 위해 자취방을 빨리 구하려고 한다. 매물번호를 이용해 자취방의 아름다움을 계산해보자!

입력

---

첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 200000)

둘째 줄에 자취방의 매물번호를 의미하는 정수 a1,a2,⋯,aN이 주어진다. (1 ≤ ai ≤ 200000)

출력

---

자취방의 아름다움을 출력한다.

 

문제 풀이

---

재귀 문제.

 

배열 S를 절반과 나머지로 나눈 후, 둘 중 하나를 선택해 그 범위에 해당하는 원소들의 GCD를 구한 후, 선택하지 않은 범위에 대해 반복하는 방법이다. 따라서 재귀를 이용해 답을 구하면 된다.

 

앞의 부분을 A라 하고, 뒤의 부분을 B라 하면, 배열 S에 대해 A의 GCD를 구하고, B를 S 삼아 재귀적으로 호출하여 해당 부분의 GCD 합의 최댓값을 구하는 경우의 수와, B의 GCD를 구하고, A를 S 삼아 재귀적으로 호출하여 해당 부분의 GCD 합의 최댓값을 구하는 경우의 수 2가지가 존재한다. 이 두가지 경우를 구하고 큰 쪽의 값을 반환해주면 된다.

기저가 되는 조건은 배열의 크기가 1인 경우이다. 이 경우는 문제에서 나온대로 해당 원소가 선택되고, GCD는 해당 원소가 된다.

배열의 크기와 다시 S로 삼은 배열이 크기 N짜리의 원래 배열에서 어느 범위에 해당하는지 left와 right를 매개변수로 삼아 A의 범위와 B의 범위를 구해 함수를 작성해주면 된다.

 

GCD는 유클리드 호제법으로 구하면 된다.

 

아래는 코드.

#include <iostream>
using namespace std;
int N;
int* arr;

int getGCD(int x, int y)
{
	if (y == 0)
	{
		return x;
	}
	else
	{
		return getGCD(y, x % y);
	}
}

int getRangeGCD(int left, int right)
{
	if (left == right)
	{
		return arr[left];
	}
	else
	{
		int gcd = getGCD(arr[left], arr[right]);
		for (int i = left + 1; i < right; i++)
		{
			gcd = getGCD(arr[i], gcd);
		}
		return gcd;
	}
}

int divide(int N, int left, int right)
{
	if (N == 1)
	{
		return arr[left];
	}
	int leftEnd = left + N / 2 - 1;
	int rightRangeCount = N - N / 2;
	int leftDivide = getRangeGCD(left, leftEnd) + divide(rightRangeCount, leftEnd + 1, right);
	int rightDivide = divide(N/2, left, leftEnd) + getRangeGCD(leftEnd + 1, right);

	return max(leftDivide, rightDivide);
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N;
	arr = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	int answer = divide(N, 0, N - 1);
	cout << answer << "\n";
	return 0;
}