[C++] 백준 21870번: 시철이가 사랑한 GCD

문제 링크

21870번: 시철이가 사랑한 GCD

문제 요약

배열 S가 주어질 때, 배열의 아름다움을 측정해야 한다. 아름다움의 측정 방법은 다음과 같다.
1. 배열 S의 왼쪽부터 $floor(|S|/2)$개의 원소를 선택하거나 오른쪽부터 $ceil(|S|/2)$개의 원소를 선택한다. (|S|는 배열 S의 원소의 수)
2. 선택한 원소들의 GCD를 구한다.
3. 선택하지 않은 원소들을 대상으로 1번부터 다시 반복한다.
4. GCD 합의 최댓값을 출력한다.

접근 방법

쉬운 분할 정복 문제입니다. 매 구간을 반으로 나눠서, 구간을 각각 선택해서 GCD를 구하고, 선택되지 않은 구간에 대해서는 재귀호출을 해서 반환값을 더해줍니다. 이렇게 반으로 나뉜 두 구간에 대한 아름다움 값이 두개 구해진다면, 둘 중 최댓값을 반환해주면 됩니다.

문제가 상당히 직관적으로 풀이를 유도하고 있어서 어렵지 않은 문제였습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int gcd(int a, int b) {
	return (a % b ? gcd(b, a % b) : b);
}

int func(vector<int>& v, int s, int e) {
	int ret = v[s];
	for (int i = s + 1; i <= e; i++)
		ret = gcd(ret, v[i]);
	return ret;
}

int divide(vector<int>& v, int s, int e) {
	if (s == e)
		return v[s];

	int m1 = s + floor((double)(e - s + 1) / 2.0) - 1;
	int m2 = e - ceil((double)(e - s + 1) / 2.0) + 1;

	int val1 = divide(v, s, m1) + func(v, m2, e);
	int val2 = divide(v, m2, e) + func(v, s, m1);
	return max(val1, val2);
}
  
int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;

	vector<int> v(n);
	for (auto& i : v) cin >> i;

	cout << divide(v, 0, v.size() - 1) << '\n';
	return 0;
}