[백준 32625] 분할 (C++)

문제

---

크기 N의 정수 배열 A가 있다. 다음 조건을 만족하도록 배열을 연속 구간으로 분할하는 것이 가능한지 판단하시오.

• 배열의 모든 원소가 정확히 하나의 구간에 포함된다.
• 각 구간의 크기는 1 이상 N 미만이며, 모든 구간의 크기는 같다.
• 각 구간에서 최솟값과 최댓값을 더한 값이 모든 구간에서 같다.

 

입력

---

첫째 줄에 배열의 크기 N이 주어진다. (2 ≤ N ≤ 100000)

둘째 줄에 A의 원소 A1,A2,A3,⋯,AN이 공백으로 구분되어 주어진다. (1 ≤ Ai ≤ N)

 

출력

---

조건을 만족하도록 배열을 분할하는 것이 가능하다면 1을, 그렇지 않다면 0을 첫째 줄에 출력한다.

 

문제 풀이

---

브루트 포스 문제.

 

각 구간의 크기가 동일하므로 구간은 N의 약수여야 한다. N의 약수를 모두 구한 후, 모든 구간의 합이 같은지 확인해주면 된다.

set에 모든 약수를 저장한 후, set을 처음부터 탐색하며 하나의 구간의 크기를 얻어온 후 각 구간의 최솟값과 최댓값의 합이 같은지 확인해준다.

 

아래는 코드.

#include <iostream>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;

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

	int N;
	cin >> N;
	int* arr = new int[N];
	set<int> div;
	set<int>::iterator it;
	bool canDivide = false;
	div.insert(1);
	for (int i = 2; i <= sqrt(N); i++)
	{
		if (N % i == 0)
		{
			div.insert(i);
			div.insert(N / i);
		}
	}
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	for (it = div.begin(); it != div.end() && canDivide == false; it++)
	{
		int count = *it;
		int pos = 0;
		int sum = -1;
		bool check = true;
		while (pos < N)
		{
			int minValue = 100001;
			int maxValue = 0;
			for (int i = pos; i < pos + count; i++)
			{
				minValue = min(minValue, arr[i]);
				maxValue = max(maxValue, arr[i]);
			}
			if (sum == -1)
			{
				sum = minValue + maxValue;
			}
			else if (sum != minValue + maxValue)
			{
				check = false;
				break;
			}
			pos += count;
		}
		if (check == true)
		{
			canDivide = true;
		}
	}
	if (canDivide == true)
	{
		cout << 1 << "\n";
	}
	else
	{
		cout << 0 << "\n";
	}
	return 0;
}